1.題目描述：點擊打開鏈接

2.解題思路：本題利用遞推關系解決。首先可以把“已經使用過的火柴數i”看做狀態，可以得到一個圖，從前往后每添加一個數字x，就從狀態i轉移到了i+c[x]，其中c[x]代表數字x需要的火柴數。當i=0時不允許使用數字0（當n≥6，給答案單獨加上1，代表整數0）。令d(i)表示從結點0到結點i的路徑條數，則答案為f(n)=d(1)+d(2)+...+d(n)。

程序實現時，我們可以按照從小到大的順序用d(i)更新所有的d(i+c[j])（j取遍數字0~9）。由于結果非常大， 需要使用高精度模板存儲結果。

3.代碼：

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>

#include<algorithm>

#include<string>

#include<sstream>

#include<set>

#include<vector>

#include<stack>

#include<map>

#include<queue>

#include<deque>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<ctime>

#include<functional>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int, int> P;

typedef pair<long long, long long> PL;

#define me(s) memset(s,0,sizeof(s))

#define For(i,n) for(int i=0;i<(n);i++)

#define N 2000+10

int n;

int c[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };

struct Node

{

int p[500];

int len;

Node()

{

me(p); len = 0;

}

Node(int a)

{

p[0] = a;

len = 1;

}

Node operator +(const Node&a)const

{

Node b;

b.len = max(len, a.len);

For(i, b.len)

{

b.p[i] += p[i] + a.p[i];

b.p[i + 1] = b.p[i] / 10;

b.p[i] %= 10;

}

if (b.p[b.len] > 0)b.len++;

return b;

}

void out()

{

if (!len)puts("0");

else{

for (int i = len - 1; i >= 0; i--)

printf("%d", p[i]);

puts("");

}

}

}d[N];

void init()

{

d[0].p[0] = 1;

d[0].len = 1;

For(i, 2001)

{

For(j,10)

if (i + c[j] < 2001 && !(i == 0 && j == 0))//i=j=0時不允許轉移

d[i + c[j]] = d[i + c[j]] + d[i];

}

d[6] = d[6] + Node(1);

for (int i = 2; i < 2001; i++)

d[i] = d[i] + d[i - 1];

}

int main()

{

//freopen("t.txt", "r", stdin);

init();

while (cin >> n)

{

d[n].out();

}

return 0;

}

總結

以上是生活随笔為你收集整理的火柴 UVa11375的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。