[POJ2229] [USACO 2005 January Silver] Sum sets
一个裸的完全背包,考虑将2k当做物品,做完全背包即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| #include <iostream> #include <cstdio> #define MAXN 1000005 #define MAXM 24 #define MOD 1000000000 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } int pow2[MAXN]; int dp[MAXN]; int main(){ int n=read(); for (register int i=0;i<MAXM;++i){ pow2[i]=(1<<i); } dp[0]=1; for (register int j=0;j<MAXM;++j){ for (register int i=1;i<=n;++i){ if (i-pow2[j]>=0){ dp[i]+=dp[i-pow2[j]]; dp[i]%=MOD; } } } printf("%d\n",dp[n]); }
|