NYOJ 325 zb的生日 【dp问题】

原文链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=325

这是一个可以用动态规划解决的题，可以看成是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]);
	}
}