nyoj_655_光棍的yy

nyoj_655_光棍的yy_201311281539

光棍的yy

时间限制：1000 ms | 内存限制：65535 KB

难度：2

描述

yy经常遇见一个奇怪的事情，每当他看时间的时候总会看见11:11，这个很纠结啊。

现在给你m个1，你可以把2个1组合成一个2，这样就不是光棍了，问这样的组合有多少种？？

例如（111 可以拆分为 111 12 21 有三种）

输入

第一行输入一个n表示有n个测试数据以下n行，每行输入m个1 (1 <= n,m <= 200)

输出

输出这种组合种数，占一行

样例输入

样例输出

2
3
8

来源

hdu

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int main()
 5 {
 6     int T,k=0,t=0;;
 7     int i,j,f[220][100];
 8     memset(f,0,sizeof(f));
 9     f[1][0]=1;
10     f[2][0]=2;
11     for(i=3;i<=200;i++)
12     {
13         for(j=0;j<=t;j++)
14         {
15             f[i][j]=f[i-1][j]+f[i-2][j]+k;
16             if(f[i][j]>9)
17             {
18                 k=1;
19                 f[i][j]-=10;
20             }
21             else
22             k=0;
23             if(k==1&&j==t)
24             t+=1;
25         }
26     }
27     scanf("%d",&T);
28     while(T--)
29     {
30         char s[220];
31         int a,n;
32         scanf("%s",s);
33         n=strlen(s);
34         for(a=99;a>0&&(f[n][a]==0);a--);
35         for(;a>=0;a--)
36         printf("%d",f[n][a]);
37         printf("
");
38     }
39     return 0;
40 }

//ac
以前wa了好多次，就是一个斐波那契数列问题，大数问题