POJ 2229 Sumsets

题目连接

题目

描述

对输入的数字，能够用2的整数幂和的形式标识，求表示的方案数。 例如数字7： 1) 1+1+1+1+1+1+1 2) 1+1+1+1+1+2 3) 1+1+1+2+2 4) 1+1+1+4 5) 1+2+2+2 6) 1+2+4 共6种表示方法；

输入

输入一个数字

样例输入：

7

输出

对应数字的答案

样例输出：

6

题解

找规律(递推)

数(奇数)结果数(偶数)结果1122324454667681091010141114

由表基本可以推断出规律： i为奇数时：a[i]=a[i-1]; i为偶数时：a[i]=a[i-1]+a[i/2]; 初始值：a[1]=1,a[2]=2;

代码(C++)

#include <iostream> using namespace std; //直接按推出的规律走，16ms,4640K //const int M = 2000000; //int a[M] = {0}; //int main(){ // int N; // cin>>N; // a[1] = 1; // a[2] = 2; // for(int i=3;i<=N;i++){ //因为输入只有一个数字，所以循环终止条件可以按输入的定 // if(i%2==1){ // a[i] = a[i-1]; // }else{ // a[i] = a[i-1] + a[i/2]; // } // if(a[i]>1000000000) //按题目要求只保留后9位结果 // a[i] -= 1000000000; // } // cout << a[N] << endl; // return 0; //} //改进版，减少空间消耗，32ms，2672K //因为若i为奇数，则a[i]=a[i-1];所以只存储偶数的答案。 const int M = 500000; int a[M] = {0}; int main(){ int N; cin>>N; a[0] = 1; a[1] = 2; for(int i=2;i<=N/2;i++){ a[i] = a[i-1]+a[i/2];//只存偶数也就不用在进行判断 if(a[i]>1000000000) a[i] -= 1000000000; } cout << a[N/2] << endl; return 0; }

运行结果

ResultAcceptedTime32msMemory2672kbLength311LanguageG++