hdu-2709整数划分技巧

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

整数划分变形，由2^k组成。

整数划分中一个节约内存的技巧，平时我们使用dp[i][j]维护用不大于j的数组合成i的方案数，所以必须dp[i-j][j]->dp[i][j]。这样就需要二位，如果用一维dp[i-j]->dp[i]就会导致重复选取的情况。其原因在于dp[i-j]在计算的过程已经把大于j的组合求完了，就会重复。那么很自然地想到把j地遍历放在外面，这样每次求解的时候，dp[i-j]必然只求解了小于等于j的情况。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define LL int
const LL mod=;
const LL N=;
LL dp[N];
LL bit[];
using namespace std;
int main()
{
cin.sync_with_stdio(false);
LL n;
int t;
bit[]=;
for(int i=;i<;i++)bit[i]=bit[i-]*;
dp[]=;
for(int i=;bit[i]<N;i++)
{
for(int j=bit[i];j<N;j++)
dp[j]+=dp[j-bit[i]],dp[j]%=mod;
}
while(cin>>n)
{
cout<<dp[n]<<endl;
}
}