2009-10-02 22:42:00來源不明
USACO C-分堆大考驗
作法: DP
有點像是採藥那樣的DP,在此感謝 andy3466 的協助
/*********************************************************/
#include<stdio.h>
#include<stdlib.h>
main()
{
int n,a,b,c;
while(scanf("%d",&n)==1)
{
int sum=0,flag=0;
int temp[50];
long long int value[5001]={0};
for(b=0;b<n;b++)
{
temp[b]=b+1;
sum=sum+temp[b];
}
if(sum%2!=0) {printf("0\n");continue;}
sum/=2;
for(b=0;b<n;b++)
for(c=sum-temp[b];c>=0;c--)
if(c==0) value[temp[b]]++;
else if(value[c]) value[c+temp[b]]+=value[c];
printf("%lld\n",value[sum]/2);
}
return 0;
}