本文主要是介绍poj 2229 (动态规划,找规律),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:求把一个整数分解为2的幂的和共有几种方案
f(1) (1)
f(2) (1 1) (2)
f(3) (1 1 1) (1 2)
f(4) (1 1 1 1) (1 1 2) (2 2) (4)
f(5) (1 1 1 1 1) (1 1 1 2) (1 2 2) (1 4)
f(6) (1 1 1 1 1 1) (1 1 1 1 2) (1 1 2 2) (1 1 4) (2 2 2) (2 4)
f(7) (1 1 1 1 1 1 1) (1 1 1 1 1 2) (1 1 1 2 2) (1 1 1 4) (1 2 2 2) (1 2 4)
。。。
发现规律了吗?
如果n是奇数那么f(n)=f(n-1) 在f(n-1)的组合前面加上1就可以了
如果n是偶数那么f(n)=f(n-1)+f(n/2),因为f(n)比f(n-1)多出的数字组合正好是f(n/2)的组合中每一位都乘以2得到的
#include<stdio.h>int main(void)
{
int f[1000001],i,N;
f[1]=1;
f[2]=2;
for(i=3;i<=1000000;i++)
{
if(i&1) //判断奇偶
f[i]=f[i-1];
else
{
f[i]=f[i-1]+f[i>>1];//i>>1位运算就是i/2
f[i]%=1000000000;
}
}
scanf("%d",&N);
printf("%d\n",f[N]);
}
这篇关于poj 2229 (动态规划,找规律)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!