题意：给你一个n，问你有多少个组合加起来可以等于n（组合里的数都是2的幂） 1 <= N <= 1,000,000
如： n=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 一共有6种方法一：用完全背包来做 因为n的范围为1000000，然后2的幂，可能取值有20个 然后递推关系式为： dp[j]=dp[j]+dp[j-a[i]]; O（20n） 然后题目说了要保留9个有效数字，应该是模1e9，还在int范围，不用用longlong，用longlong就会超时
#include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <cstdio> using namespace std; const int maxn = 1000005; int dp[maxn]; int n; int a[25]; int g=1000000000; int pow1(int k) { int sum=1; for(int i=1;i<=k;i++) sum*=2; return sum; } void solve() { for(int i=0;i<21;i++){ a[i+1]=pow1(i); if(a[i+1]>1000000) break; } dp[0]=1; for(int i=1;i<=21;i++) { if(a[i]>n) break; for(int j=0;j<=n;j++) { if(j>=a[i]) dp[j]=(dp[j]+dp[j-a[i]])%g; } } printf("%d\n",dp[n]%g); } int main() { scanf("%d",&n); solve(); return 0; }方法二 O（n） 当n为奇数时，dp[n] = dp[n-1],因为一定包含一个1，所以dp[n-1]的每一种再加1都一一对应着dp[n];当n为偶数时，要么至少含2个1，或者不含1，不含1时，方法数就是取dp[n/2]的每一种物品乘以2价值的物品。所以dp[n] = dp[n-1] + dp[n/2]。
#include <iostream> #include <cstring> #include <algorithm> #include <cmath> #include <cstdio> using namespace std; const int maxn = 1000005; int dp[maxn]; int n; int g=1000000000; void solve() { dp[0]=1; for(int i=1;i<=n;i++) { if(i%2==1) dp[i]=dp[i-1]; else dp[i]=(dp[i-1]+dp[i/2])%g; } printf("%d\n",dp[n]); } int main() { scanf("%d",&n); solve(); return 0; }