usaco 2.2 Subset Sums

这个题就是一个dp问题
我们用data[i][j]表示前i个数字构成j的方案数
这样的话可以得到状态转移方程
data[i][j]=data[i-1][j-i]+data[i-1][j];
边界条件就是当j等于0的时候data[i][j]=1;
当i等于0的时候j不等于0data[i][j]=0;
然后提交的时候忘记测39这个数据了造成wa了一次
因为求出来的是需要除2的
而39这个数据的答案乘以2以后超过了int
在计算过程中用int64或是unsigned int都是可以的。
我选用了unsigned int这个
因为对g++的int64用哪个一直比较混乱
记得以前写是用long long最近又听说用__int64

 1/**//*
 2ID: bnugong1
 3PROG: subset
 4LANG: C++
 5*/
 6#include<stdio.h>
 7#include<string.h>
 8unsigned int data[40][800];
 9void di(int i,int j)
10{
11    unsigned int ans;
12    if(j==0){
13        data[i][j]=1;
14        return;
15    }
16    if(i==0){
17        data[i][j]=0;
18        return;
19    }
20    if(data[i-1][j]==(unsigned int)-1)di(i-1,j);
21    ans=data[i-1][j];
22    if(j-i>=0){
23        if(data[i-1][j-i]==(unsigned int)-1)di(i-1,j-i);
24        ans+=data[i-1][j-i];
25    }
26    data[i][j]=ans;
27//    printf("%d\n",ans);
28    return;
29}
30int main()
31{
32    int n,sum;
33    freopen("subset.in","r",stdin);
34    freopen("subset.out","w",stdout);
35    scanf("%d",&n);
36    sum=((n+1)*n)/2;
37    if(sum%2==1)printf("0\n");
38    else
39    {
40        memset(data,-1,sizeof(data));
41        sum=sum/2;
42        di(n,sum);
43        printf("%u\n",data[n][sum]/2);
44    }
45    return 0;
46}
47

posted on 2008-07-19 02:58 gong 阅读(897) 评论(0)  编辑 收藏 引用