1sting
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3997 Accepted Submission(s): 1489
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
#include<stdio.h> #include<string.h> char s[210]; int num[210][1000]; int len[1000]; int main() { int n; int i,j,k,l,m; memset(num,0,sizeof(num));//二维数组也可以这样初始化 num[1][0]=1; num[2][0]=2;//初始斐波那契数前两位 len[1]=len[2]=1;//储存大数的位数 l=0; for(i=3;i<210;i++) { k=0; for(j=0;j<=len[i-1];j++) { l=k+num[i-1][j]+num[i-2][j]; num[i][j]=l%10; k=l/10; } //用第一维储存斐波那契数第二维储存位数（如果你先把大数相加就是杭电1002和大数相乘1042做过之后这里就很好理解啦） if(num[i][len[i-1]]!=0) len[i]=len[i-1]+1; else len[i]=len[i-1];//此处是标记第一个非零数的位置（就是去零） } scanf("%d",&n); getchar(); while(n--) { //getchar(); scanf("%s",s); m=strlen(s); for(i=len[m]-1;i>=0;i--) printf("%d",num[m][i]); printf("\n"); } return 0; }
题目总结： 此题是斐波那契数列与大数相加的结合，此解法是利用二维数组对数据进行处理
