?數(shù)的集合問題

　　題目大意：給定你一個整數(shù)m，你只能用2的k次冪來組合這個數(shù)，問你有多少種組合方式？

　　這一題一看，天啦太簡單了，完全背包？是不是？

　　不過的確這一題可以用完全背包來想，但是交題絕對是TLE，如果真的是完全背包的做法那我就不用等那么多天再發(fā)這個坑，這一題的確要用到點奇妙的思想。

　　首先，我們忽略了這一題的最重要的一個條件，我們使用的數(shù)就是2次冪的，那么2次冪的數(shù)可以做什么呢？這就是一個數(shù)學(xué)問題了

　　不過不要怕，這個數(shù)學(xué)問題也很好想，

　　　　首先：任何一個奇數(shù)一定有1來組成，推論：任何偶數(shù)都可以只由除了1的數(shù)組成

　　　　其次，任何一個偶數(shù)都可以由一個數(shù)左移1來得到（參考二進(jìn)制）

　　下面我們就用這兩個數(shù)學(xué)結(jié)論來思考怎么簡化遞推。

　　回到問題上來，完全背包會TLE的原因是出在在第二個循環(huán)的時候?qū)進(jìn)行了過多的枚舉，那么我們在用這兩個結(jié)論的時候必須避開這一點，最好一步到位，所以我們必須把個數(shù)全部壓在前一次的情況上，那么我們可首先用結(jié)論1，對于任何一個奇數(shù)，我們都可以用上一個偶數(shù)+1（組合數(shù)不變，因為只能加這個1），且這個集合不能由其他集合直接得到，那么我們就得到第一個遞推公式

　　　dp[j]=dp[j-1] ?當(dāng)j=奇數(shù)

　　現(xiàn)在用到第二個結(jié)論，因為我們的偶數(shù)可以從奇數(shù)得到，也可以從偶數(shù)得到，那么可以第一部分可以從dp[j-1]得到，另外一個部分就要思考結(jié)論2，因為我們只是左移，組合數(shù)是不變的，所以我們還可以從dp[j>>1]中得到另一部分的組合數(shù)，這樣就避開了一個一個查找枚舉i的背包了

　　所以綜上，狀態(tài)轉(zhuǎn)移方程為：

　　　　dp[i]=dp[i-1] ?當(dāng)i是奇數(shù)

　　　　dp[i]=dp[i-1]+dp[i>>1] ?當(dāng)i是偶數(shù)　　

　　　　（注意這一題只顯示9個數(shù)字）

1 #include <stdio.h> 2 #include <stdlib.h> 3 #define M 1000000000 4 5 long long Combinatories[1000001]; 6 7 int main(void)//這一題不能用完全背包，會超時 8 { 9 int N, i; 10 Combinatories[1] = 1;//這個地方要設(shè)置成1 11 12 for (i = 2; i < 1000001; i++) 13 { 14 if (i % 2 == 1) 15 Combinatories[i] = Combinatories[i - 1]; 16 else 17 Combinatories[i] = Combinatories[i - 1] + Combinatories[i >> 1]; 18 Combinatories[i] %= M; 19 } 20 21 while (~scanf("%d", &N)) 22 printf("%d\n", Combinatories[N] % M); 23 24 return 0; 25 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Philip-Tell-Truth/p/4840906.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。