杭電1865-1 sting

1sting
Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4133    Accepted Submission(s): 1547
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
 
 
Author
z.jt
 
 
Source
2008杭電合宿チーム選抜試合——ウォーミングアップ試合
 
 
Recommend
lcy   |   We have carefully selected several similar problems for you:  
1715  
1250  
1133  
2100  
1753  
//考え方: プッシュ数には1と2の2つの数字→→→f(n)=f(n-1)+f(n-1)しか存在しない.

 1 #include <stdio.h>
 2 #include <string.h>
 3 int fei[220][1001];
 4 int main()
 5 {
 6     int n;
 7     char str[220];
 8     int i, j;
 9     int temp, plus = 0;
10     memset(fei, 0, sizeof(fei));
11     fei[1][0] = 1;
12     fei[2][0] = 2; 
13     for(i=3; i<201; i++)  
14     {
15         for(j=0; j<1001; j++)     //            ；
16         {
17             temp = fei[i-1][j] + fei[i-2][j] + plus;
18             fei[i][j] = temp%10;
19             plus = temp/10;
20         }
21     }
22     scanf("%d", &n);
23     while(n--)
24     {
25         scanf("%s", str);
26         int len = strlen(str);
27         for(i=1000; i>=0; i--)
28         if(fei[len][i])
29         break;
30         for(; i>=0; i--)
31         printf("%d", fei[len][i]);
32         printf("
");
33     }
34     return 0;
35 }