首页 > 代码库 > poj 2220 Sumsets
poj 2220 Sumsets
Sumsets
| Time Limit: 2000MS | Memory Limit: 200000K | |
| Total Submissions: 16876 | Accepted: 6678 |
Description
Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7:
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4
Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4
Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).
Input
A single line with a single integer, N.
Output
The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation).
Sample Input
7
Sample Output
6
初学动态规划，我用了一种非常愚蠢的解法耗内存又超时了...
AC代码：
#include<iostream>#include<algorithm>using namespace std;int dp[1000000+1];/*const int N_MAX = 1000000;int dp[21][N_MAX + 1];int main() { int N; while (cin >> N) { int k = 0; while ((1 << k) <= N) {//求使得2^k大于N的最小k k++; } for (int i = 0;i < k;i++) dp[i][0] = 0; for (int i = 1;i <= N;i++) dp[0][i] = 1; for (int i = 1;i < k;i++) { for (int j = 1;j <= N;j++) { dp[i][j] = dp[i - 1][j]; for (int k1 = 1;(j - k1*(1 << i))>=0;k1++) { dp[i][j] += dp[i - 1][j - k1*(1 << i)]; } } } cout << dp[k-1][N] << endl; } return 0;}*///若i为奇数,(i-1)为偶数，i的组合数就是(i-1)的组合数，因为(i-1)只能加1得到i。若i为偶数，(i-1)为奇数，则通过(i-1)+1的方式得到i的组合必定带有1，接下来考虑//全是偶数的组合数，考虑到全是偶数的组合数和(i/2)的组合数一样，因为只要(i/2)的组合数里每一个数*2就可以得到iint main() { int N; while (cin >> N) { dp[1] = 1; for (int i = 2;i <= N;i++) { if ((i & 1)==0) {//若为偶数 dp[i] = dp[i / 2]; } dp[i] += dp[i - 1]; dp[i] %= 1000000000; } cout << dp[N] << endl; } return 0;}
poj 2220 Sumsets
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。