2018-2-2

首先我們不難看出：
當n為奇數時，dp[n]=dp[n-1]，因為它無論如何都會有1在里面。
當n為偶數時，我們通過題意可以看出，它的序列是無序的，換言之，1,1,2和2,1,1是相同的，只要保證它的序列是遞增的，那么我們就可以不重復的求出它的個數。

#include<iostream> #include<cstring> using namespace std;const int N = 1000000; int dp[N+1]; int x[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};int main(){int i,j,n;while (cin>>n){memset(dp,0,sizeof(dp));dp[0]=1;dp[1]=1;for (i=0;i<20;i++){for (j=x[i];j<=n;j++){if (j%2!=0) dp[j]=dp[j-1];else dp[j]=(dp[j]+dp[j-x[i]])%1000000000;//求得的當前的dp[j]就是以x[i]為結尾的個數。}}cout<<dp[n]<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的poj2229 基础的动态规划算法 挑战程序设计竞赛的全部內容，希望文章能夠幫你解決所遇到的問題。

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