Blog·Tanky WooABOUTRSS

HDU/HDOJ 1041 Computer Transformation

09 May 2011
这篇博客是从旧博客 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;
}