HDU 1297 Children’s Queue

题目:http://acm.hdu.edu.cn/showproblem.php?pid=1297

同样递推,不过用了大数

#include <iostream>
#include <string>

using namespace std;


string add(const string &a,const string &b)
{
    int dig = 0;//½øλ·û
    string a1,b1;
    if(a.size()>b.size())
    {
        a1 = a;
        b1 = b;
    }else
    {
        a1 = b;
        b1 = a;
    }
    int clen = a1.size() - b1.size();
    for (int i = 0; i < clen ; i++)
    {
        string zero(1,'0');
        b1.insert(0,zero);
    }
    for (int i = a1.size() - 1; i >= 0 ; i--)
    {
        int t = (int)a1[i] + (int)b1[i] - '0' - '0';
        a1[i] = char(( t + dig)%10 + '0');
        dig = ( t + dig) /10;
    }
    if(dig!=0)
    {
        string d(1,char(dig+48));
        a1.insert(0,d);
    }
    return a1;
}

int main()
{


    string res[1001]={"0","1","2","4","7"};
    for(int i=5; i<1001; i++)
    {
        res[i] = add(res[i-1],res[i-2]);
        res[i] = add(res[i],res[i-4]);
        //cout<<res[i]<<endl;
    }


    int n;
    while(cin>>n)
    {
       // if(n>101) {n/=0;continue;}
        cout<<res[n]<<endl;
    }
    return 0;
}