首页 > 代码库 > 【noi 2.6_7113】Charm Bracelet（DP）
【noi 2.6_7113】Charm Bracelet（DP）
题意：N个饰物，有重量和渴望程度。问在Ｍ的重量限制内能达到的最大的渴望度。
解法：经典的01问题，但有一个小技巧值得记住：用if比较大小比调用max函数快了不少，这题有100ms左右。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 #define VV 12900 7 int w[VV],d[VV],f[VV]; 8 9 int main()10 {11 int n,V;12 scanf("%d%d",&n,&V);13 for (int i=1;i<=n;i++)14 scanf("%d%d",&w[i],&d[i]);15 memset(f,0,sizeof(f));16 for (int i=1;i<=n;i++)17 for (int j=V;j>=w[i];j--)18 if (f[j-w[i]]+d[i]>f[j]) f[j]=f[j-w[i]]+d[i];19 printf("%d\n",f[V]);20 return 0;21 }
【noi 2.6_7113】Charm Bracelet（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。