hdu1865（高精度，找规律）

1sting

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2599    Accepted Submission(s): 1032

Problem Description You will be given a string which only contains ‘1’; You can merge two adjacent ‘1’ to be ‘2’, or leave the ‘1’ there. Surly, you may get many different results. For example, given 1111 , you can get 1111, 121, 112,211,22. Now, your work is to find the total number of result you can get.

Input The first line is a number n refers to the number of test cases. Then n lines follows, each line has a string made up of ‘1’ . The maximum length of the sequence is 200.

Output The output contain n lines, each line output the number of result you can get .

Sample Input

3
1
11
11111
        

Sample Output

1
2
8
        

找递推关系，末尾可以是1或者2，是1的时候为f(x-1)，是2的时候为f(x-2)；

这样f(x0=f(x-1)+f(x-2)； 斐波那契数列

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int MAXN = 500, MAXM = 250;
int ans[MAXN][MAXM];

void init(){
    ans[1][0]=1;
    ans[2][0]=2;
    for(int i=3; i<MAXN; i++){
        for(int j=0; j<MAXM; j++){
            ans[i][j]+=ans[i-1][j]+ans[i-2][j];
            if(ans[i][j]>9){ans[i][j+1]+=ans[i][j]/10; ans[i][j]%=10;}
        }
    }
}

void print(int n){
    int i = MAXM-1;
    while(ans[n][i]==0) i--;
    while(i!=-1) cout<<ans[n][i--];
    cout<<endl;
}

int main()
{
    init();
    int t;
    string str;
    cin>>t;
    while(t--){
        cin>>str;
        print(str.size());
    }
    return 0;
}