題目鏈接

題意

給定一個數字，問用2的次方數湊，一共有幾種情況
例如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種情況

AC

• 完全背包

int dp[N]; //long long超時。。。 int mod = 1e9; int main(){ #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifint n;cin >> n;int a[22];for (int i = 0; i < 22; i++) {a[i] = 1 << i;}dp[0] = 1;for (int i = 0; i < 22; i++) {if (a[i] > n) break;for (int j = a[i]; j <= n; ++j) {dp[j] += dp[j - a[i]];dp[j] %= mod;}}cout << dp[n] << endl;return 0; }

• 規律
  

using namespace std; int dp[N]; int mod = 1e9; int main(){ #ifndef ONLINE_JUDGE// freopen("in.txt", "r", stdin); #endifint n;cin >> n;dp[1] = 1;dp[2] = dp[3] = 2;for (int i = 4; i <= 1000000; ++i) {if (i > n) break;if (i % 2) dp[i] = dp[i - 1] % mod;else dp[i] = (dp[i - 2] % mod + dp[i / 2] % mod) % mod;}cout << dp[n] << endl;return 0; }

總結

以上是生活随笔為你收集整理的POJ 2229 Sumsets的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。