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\n");

continue;

}

for(;i >= 1;i --)

printf("%d" ,Ans[n][i]);

printf("\n");

}

return 0;

}

巴特西

UVA11375火柴(递推+大数)

最新文章

热门文章