这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1041
找递推关系~~~
ans[i-1]*2+1 (i%2==0)
ans[i]={
ans[i-1]*2-1 (i%2==1)
也可以换成:
ans[i] = ans[i-1] + 2*ans[i-2]
代码:
#include
#include
#include
using namespace std;
int s[1005][505];
int num, jinwei = 0;
int main()
{
s[0][1] = 0;
s[1][1] = 0;
s[2][1] = 1;
s[3][1] = 1;
for(int i=4; i<=1000; ++i)
{
for(int j=1; j<=500; ++j)
{
s[i][j] = s[i-1][j] + 2*s[i-2][j] + jinwei;
jinwei = s[i][j] / 10;
s[i][j] %= 10;
}
}
while(cin >> num)
{
if(num == 1)
{
cout << 0 << endl;
continue;
}
int i;
for(i=500; i>0; --i)
if(s[num][i] != 0)
break;
for(int j=i; j>=1; --j)
cout << s[num][j];
cout << endl;
}
return 0;
}