HDU-1865-1sting

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;
}

题目总结： 此题是斐波那契数列与大数相加的结合，此解法是利用二维数组对数据进行处理
num[m][i] 第一维 m 是表示第几个斐波那契数 第二维 i 是表是第 m 个数的位数