題意：

? ? ? 給你n根火柴，問你能組成多少種數(shù)字，比如3根可以組成1或者7，組成的數(shù)字中不能有前導(dǎo)0，

思路：
? ? ? 我們開一個數(shù)組，d[i]記錄用i跟火柴可以組成多少種數(shù)字，則更新狀態(tài)是這樣的
d[i+c[j]] += d[i], c[j]就是組成數(shù)字j要用的火柴數(shù)，這樣跟新相當(dāng)于是在模擬寫數(shù)字，但是有一點就是不能以0開頭，左后當(dāng)火柴數(shù)大于等于6的時候就可以在總答案上+1，表示可以構(gòu)成一個單獨的0（因為之前沒有0開頭的，所以要+1補回來），最后答案就是
Ans[n] = d[1] + d[2] + d[3] + .... + d[n],因為火柴可以不全部用完，還有就是數(shù)據(jù)比較大，要用大數(shù)模擬，這個就不解釋了。






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

總結(jié)

以上是生活随笔為你收集整理的UVA11375火柴(递推+大数)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。