HDU/HDOJ 1041 Computer Transformation

题目传送门: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]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <string>
#include <algorithm>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注