UVA - 11375 Matches

題意：求用n個火柴能組成幾個非負整數，火柴不必用完，前導0是不能存在的

思路：把“已經用過火柴數i”表示狀態，以後每添加一個數字x就轉移狀態i到i+c[x](c[x]表示x 用到的火柴數)，因為沒有前導0，所以狀態為0的時候是不能添加數字0的（最後當n>=6的時候再添加一個代表0）

令d[i]表示到i狀態的個數，利用加法原理，因為可以不必用完火柴，所以答案是：

d[1]+...d[n]

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 510;

struct node{
    int p[MAXN];
    int len;
    node(){
        memset(p,0,sizeof(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 (int i = 0; i < b.len; i++){
            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 == 0)
            printf("0\n");
        else {
            for (int l = len-1; l >= 0; l--)
                printf("%d",p[l]);
            printf("\n");
        }
    }
}d[2005];
int c[] = {6,2,5,5,4,5,6,3,7,6};

int main(){
    d[0].p[0] = 1,d[0].len = 1;
    for (int i = 0; i < 2001; i++)//前導0不行
        for (int j = 0; j < 10; j++)
            if (!(i==0 && j==0) && i+c[j] < 2001)
                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 n;
    while (scanf("%d",&n) != EOF && n > 0)
        d[n].out();
    return 0;
}