[问题] 试找出1~N 有几种挑数字的方法(子集)不包

楼主: asdfg1597860 (Jay)   2018-08-27 12:09:14
开发平台(Platform): (Ex: Win10, Linux, ...)
编译器(Ex: GCC, clang, VC++...)+目标环境(跟开发平台不同的话需列出)
额外使用到的函数库(Library Used): (Ex: OpenGL, ...)
问题(Question):
各位高手好 小弟写了一个程式想解这个问题(政大解题系统上的题目)
但在最后一个查验点失败了
想请问各位高手能告诉小弟犯了什么愚蠢错误
因为小弟看了很多次还是觉得可行
喂入的资料(Input):
1<=n<=10^7
预期的正确结果(Expected Output):
245459220446488920
错误结果(Wrong Output):
-1
程式码(Code):(请善用置底文网页, 记得排版,禁止使用图档)
#include <iostream>
using namespace std;
long long int pow(unsigned int a) {
if (a == 0)
return 1;
else
return 2* pow(a-1);
};
int main()
{
unsigned int input,odditem,evenitem;
while(cin>>input){
if (input % 2 == 0){
evenitem = (input / 2);
odditem = evenitem;
}
else {
evenitem = (input - 1) / 2;
odditem = (input + 1) / 2;
}
cout << pow(odditem) + pow(evenitem) - 1 << endl;
}
return 0;
}
补充说明(Supplement):
什么数字都没选也算一种
作者: john2007 (john)   2018-08-27 13:49:00
想法是错的 n = 4的时候正确答案是8 你的输出结果是7而用简单的观察法可以知道你2的觅次 碰到1e7会爆掉给个提示,用DP 取/不取的分法 应该解得出来{1, 4}
作者: cutekid (可爱小孩子)   2018-08-27 18:58:00
f(n) = f(n - 1) + f(n - 2)
作者: oToToT (屁孩)   2018-08-29 16:01:00
楼上那就是本题的答案啊,只是f(1)=2,f(2)=3
作者: Sidney0503 (Sidney0503)   2018-08-31 09:27:00
有Prob_Solve版

Links booklink

Contact Us: admin [ a t ] ucptt.com