POJ 2229 Sumsets——完全背包

POJ 2229 Sumsets——完全背包

#include #include #include #include using namespace std;const int maxn = 1e6 + 5;const int mod = 1e9;int a[32], dp[maxn];int main() { a[0] = 1; for (int i = 1; i <= 20; i++) a[i] = a[i - 1] * 2; dp[0] = 1; for (int i = 0; i <= 20; i++) { for (int j = a[i]; j < maxn; j++) { dp[j] = (dp[j] + dp[j - a[i]]) % mod; } } int n; while (~scanf("%d", &n)) printf("%d\n", dp[n]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。