被动态规划玩儿坏了。。。
首先说明思路:
每一个数都可以拆成2的次幂的形式,2的次幂有(1,2,4,6,8...),其中只包括一个奇数,那就是1。
假设给定一个数N:
1.N是奇数,那么N拆分的时候必定有一个1,因为2的次幂除了1都是偶数,由很多偶数不可能构成奇数。
所以 f(N)=f(N-1)
举例:
5=(1+4)=(1+2+2)=(1+1+1+2)=(1+1+1+1+1) ;一共有四种拆分形式
4=(4) =(2+2) =(1+1+2) = (1+1+1+1) ;一共四种拆分方式
2.N是偶数,那么可以分成两种情况:
2.1 N中拆分出1,N中拆分出1和上边N是奇数的情况一样,即f(N-1)
举例:
4=(4)=(2+2)=(1+1+2)=(1+1+1+1)
3=(1+2)=(1+1+1)
2.2 N中不拆分出1
不拆分出1,即都是偶数,偶数的性质可知,偶数都可以整除2,假如N的和为2m,那么除2之后变成m,但是并不影响f(N)。
举例:
4=(4)=(2+2) 都不包含1
同理,由2.1和2.2两种情况的结果相加得到完整的4的拆分。
也就是说N为偶数的情况就是f(N)=f(N-1)+f(N/2)---------------好看一点儿就是:f(2m)=f(2m-1)+f(m);
#include<iostream> using namespace std; int dp[1000001]; int main(){ int n; dp[0]=1; while(cin>>n){ for(int i=1;i<=n;i++){ if(i%2==0){ dp[i]=(dp[i-1]+dp[i/2])%1000000000; }else{ dp[i]=dp[i-1]%1000000000; } } cout<<dp[n]<<endl; } return 0; }