2009-03-06 19:47:15來源不明
2008 TOI 研習營初選 TOI2008 3. 加減問題
DP(半個背包問題@@)
總和為奇數的話一定沒辦法配到YES
若為偶數的話,則我們就必須嘗試是否能配到1半的總和
這題提供數據很小的寫法,待網友幫解...
/************************************************************/
#include<stdio.h>#include<stdlib.h>
main()
{
int m,n,a,b,c;
while(scanf("%d %d",&m,&n)==2)
{
for(a=0;a<m;a++)
{
int sum=0,flag=0;
int temp[101]={0},value[10001]={0};
for(b=0;b<n;b++)
{
scanf("%d",&temp[b]);
sum=sum+temp[b];
}
if(sum%2==1)
{printf("No\n");continue;}
sum=sum/2;
for(b=0;b<n;b++)
{
for(c=sum-temp[b];c>=0;c--)
if(value[c+temp[b]]<=value[c]+temp[b])
{
value[c+temp[b]]=value[c]+temp[b];
if(value[c+temp[b]]==sum)
flag=1;
}
}
if(flag==1)
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}