POJ 2229 – Sumsets [动规]

比较好的动规思路题,要根据奇偶找出递推式来。

对于dp[i],当i为奇数时,相当于在dp[i-1]的每种情况前面都加上1,即dp[i] = dp[i-1]

当i为偶数时,对每种拆分,分为前面带1和不带1两种情况。带1时,可变为dp[i] = dp[i-1](或dp[i] = dp[i-2]),不带1时,由于每个数都为2的倍数,情况书相当于每个数除以2时的情况数,即dp[i] = dp[i/2]。综上所述,dp[i] = dp[i-1] + dp[i/2]。

题目要求输出结果的后9位,每次计算对1000000000取余即可,不要忘掉。

#include <iostream>
using namespace std;

int dp[1024000] = {0, 1, 2};
int main(){
    int n; cin >> n;
    for(int i = 3; i <= n; ++i){
        if(i & 1) dp[i] = dp[i-1];
        else dp[i] = (dp[i-1] + dp[i/2]) % 1000000000;
    }
    cout << dp[n] << endl;
    return 0;
}

 

欢迎留言