首页 > 代码库 > POJ 2229 计数DP
POJ 2229 计数DP
dp[i]代表是数字i的最多组合数
如果i是一个奇数,i的任意一个组合都包含1,所以dp[i] = dp[i-1]如果i是一个偶数,分两种情况讨论,一种是序列中包含1,因此dp[i]=dp[i-1]
一种是序列不包含1,那么序列中的数都是2的倍数,把他们都除以2,序列与i/2序列相同,得到dp[i]=dp[i-1]+dp[i>>1]
1 #include <cstdio> 2 using namespace std; 3 int dp[1000000 + 10]; 4 int main(){ 5 int n; 6 scanf("%d", &n); 7 dp[1] = 1; 8 dp[2] = 2; 9 for(int i = 3; i <= n; i++)10 if(dp[i] & 1)11 dp[i] = dp[i-1];12 else13 dp[i] = (dp[i-2] + dp[i>>1])%1000000000;14 printf("%d\n", dp[n]);15 return 0;16 }
POJ 2229 计数DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。