首页 > 代码库 > 题解:UESTC1218 Pick The Sticks
题解:UESTC1218 Pick The Sticks
题意:选择长度为ai,价值为vi金条覆盖长度为L的区域,使总价值最大,只要金条重心在区域内即可。
1<=N<=1000;1<=L<=2000;1<=ai<=2000;1<=vi<=109.
共1~100组数据,10000MS
注意:0/1背包的简单变形:显然最多有2次机会让金条在长度变为一半的情况下价值不变,为了避免0.5的出现,将长度,价值都乘上2,DP[i][j][k]表示选择到第i个金条,占用长度为j且已经用了k次机会时最大价值,复杂度O(3*NL).
注意特判只用一根金条时,显然无论金条多长,重心都可在区域内。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=4400; int t,n,l; long long a[maxn+5],v[maxn+5]; long long dp[maxn+5][4]; int main(){ scanf("%d",&t); for (int q=1;q<=t;++q){ scanf("%d%d",&n,&l); for (int i=1;i<=n;++i) {scanf("%lld%lld",&a[i],&v[i]);a[i]=a[i]*2;}; memset(dp,0,sizeof(dp)); for (int i=1;i<=n;++i) for (int j=2*l;j>=a[i]/2;--j){ for (int k=2;k>=1;--k){ if (j-a[i]>=0) dp[j][k]=max(dp[j][k],dp[j-a[i]][k]+v[i]); dp[j][k]=max(dp[j][k],dp[j-a[i]/2][k-1]+v[i]); } if (j-a[i]>=0) dp[j][0]=max(dp[j][0],dp[j-a[i]][0]+v[i]); } long long ans=0; for (int i=1;i<=2*l;++i) ans=max(ans,dp[i][2]); for (int i=1;i<=n;++i) ans=max(ans,v[i]); printf("Case #%d: %lld\n",q,ans); } return 0; }
题解:UESTC1218 Pick The Sticks
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。