前端之家收集整理的这篇文章主要介绍了
NYOJ 325 zb的生日 【dp问题】，
前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
这是一个可以用动态规划解决的题，可以看成是01背包的变形吧。。尽管出题人原意可能是让我们用搜索做的，但由于时间卡的不紧，于是我们可以水过。。。。本人用dp以2996ms水过（题目时间限制是3000ms）。。ac后看看本题排名就悲剧了，倒数第一。。⊙﹏⊙。。
不扯废话了，看代码吧。。
- #include<stdio.h>
- #include<algorithm>
- int main()
- {
- int a,b,n,m,v;
- while(scanf("%d",&v)!=EOF)
- {
- int yi[100001]={0};
- int ok[10000];
- int sum=0,sum1;
- for(a=1;a<=v;a++)
- {
- scanf("%d",&ok[a]);
- sum+=ok[a];
- }
- sum1=sum/2;
- for(b=1;b<=v;b++)
- {
- for(m=sum1;m>=ok[b];m--)
- {
- if(yi[m]<(yi[m-ok[b]]+ok[b]))
- yi[m]=yi[m-ok[b]]+ok[b];
-
- }
- }
- printf("%d\n",sum-2*yi[sum1]);
- }
- }
-
