UVA11375火柴(递推+大数)

题意：

      给你n根火柴，问你能组成多少种数字，比如3根可以组成1或者7，组成的数字中不能有前导0，

思路：
      我们开一个数组，d[i]记录用i跟火柴可以组成多少种数字，则更新状态是这样的
d[i+c[j]] += d[i], c[j]就是组成数字j要用的火柴数，这样跟新相当于是在模拟写数字，但是有一点就是不能以0开头，左后当火柴数大于等于6的时候就可以在总答案上+1，表示可以构成一个单独的0（因为之前没有0开头的，所以要+1补回来），最后答案就是
Ans[n] = d[1] + d[2] + d[3] + .... + d[n],因为火柴可以不全部用完，还有就是数据比较大，要用大数模拟，这个就不解释了。






#include<stdio.h>
#include<string.h>


#define N 2000 + 5


int d[N][1000];
int Ans[N][1000];


void solve()
{
   int i ,j;
   int c[] = {6,2,5,5,4,5,6,3,7,6};
   memset(d ,0 ,sizeof(d));
   d[0][1] = 1;
   for(i = 0 ;i <= 2000 ;i ++)
   for(j = 0 ;j <= 9 ;j ++)
   {
      if(!(i==0&&j==0) && i+c[j] <= 2000)
      {
         //d[i+c[j]] += d[i];
         for(int k = 1 ;k <= 888 ;k ++)
         d[i+c[j]][k] += d[i][k];
         for(int k = 1 ;k <= 888 ;k ++)
         {
            d[i+c[j]][k+1] += d[i+c[j]][k] / 10;
            d[i+c[j]][k] %= 10;
         }
      }
   }
   
   for(i = 1 ;i <= 2000 ;i ++)
   {
      if(i == 1)
      {
         for(j = 1 ;j <= 888 ;j ++)
         Ans[i][j] = d[i][j];
         continue;
      }
      //Ans[i] = Ans[i-1] + d[i];
      for(j = 1 ;j <= 888 ;j ++)
      Ans[i][j] = Ans[i-1][j] + d[i][j];
      for(j = 1 ;j <= 888 ;j ++)
      {
         Ans[i][j+1] += Ans[i][j] / 10;
         Ans[i][j] %= 10;
      }
   }
      
   for(i = 6 ;i <= 2000 ;i ++)
   {
      Ans[i][1] ++;
      if(Ans[i][1] >= 10)
      for(int k = 1 ;k <= 888 ;k ++)
      {
         Ans[i][k+1] += Ans[i][k] / 10;
         Ans[i][k] %= 10;
      }
   }
}


int main ()
{
   int n ,i ,j;
   solve();
   while(~scanf("%d" ,&n))
   {
      for(i = 888 ;i >= 1 ;i --)
      if(Ans[n][i]) break;
      if(i == 0)
      {
         printf("0 ");
         continue;
      }
      for(;i >= 1;i --)
      printf("%d" ,Ans[n][i]);
      printf(" ");
   }
   return 0;
}