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 閱讀(907) 評論(0)  編輯 收藏 引用