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)

输出

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

样例输入

3

11

111

11111

样例输出

2

3

8

来源

hdu

 #include <stdio.h>

 #include <string.h>

 int main()

 {

     int T,k=,t=;;

     int i,j,f[][];

     memset(f,,sizeof(f));

     f[][]=;

     f[][]=;

     for(i=;i<=;i++)

     {

         for(j=;j<=t;j++)

         {

             f[i][j]=f[i-][j]+f[i-][j]+k;

             if(f[i][j]>)

             {

                 k=;

                 f[i][j]-=;

             }

             else

             k=;

             if(k==&&j==t)

             t+=;

         }

     }

     scanf("%d",&T);

     while(T--)

     {

         char s[];

         int a,n;

         scanf("%s",s);

         n=strlen(s);

         for(a=;a>&&(f[n][a]==);a--);

         for(;a>=;a--)

         printf("%d",f[n][a]);

         printf("\n");

     }

     return ;

 }

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