「UVa 11375」Matches - 递推

发表于 | 分类于

有 个火柴，用这些火柴能摆出非负整数，摆出的数不能有前导零，火柴不必用完，求方案总数。

链接

UVa 11375

题解

首先考虑不存在数字 0 的情况，用 表示用 个火柴棒能摆出的方案总数，用 表示摆出数字 x 使用的火柴棒数量。

前导零是不被允许的，所以初始状态要把 1 ~ 9 几个数字的方案数加一。

每次递推用 去更新 （），表示在 表示的数字尾部添加一个 所得的方案。

递推计算完成后求出前缀和 即为答案，如果 则需要将答案加一（考虑单独的数字 0）。

需要使用高精度。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

const int MAXT = 100;
const int MAXN = 2000;
const int C[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };

struct BigInt {
    std::vector<char> v;

    BigInt() {}

    BigInt(int x) {
        *this = x;
    }

    BigInt &operator=(int x) {
        v.clear();
        do v.push_back(x % 10); while (x /= 10);
    }
};

std::ostream &operator<<(std::ostream &out, const BigInt &x) {
    const std::vector<char> &v = x.v;
    for (int i = v.size() - 1; i >= 0; i--) out << (char)(v[i] + '0');
    return out;
}

BigInt operator+(const BigInt &a, const BigInt &b) {
    BigInt r;
    r.v.reserve(std::max(a.v.size(), b.v.size()) + 1);

    bool flag = false;
    for (int i = 0; i < std::max(a.v.size(), b.v.size()); i++) {
        int tmp = 0;
        if (i < a.v.size()) tmp += a.v[i];
        if (i < b.v.size()) tmp += b.v[i];
        if (flag) tmp++, flag = false;
        if (tmp >= 10) tmp -= 10, flag = true;
        r.v.push_back(tmp);
    }
    if (flag) r.v.push_back(1);

    return r;
}

BigInt &operator+=(BigInt &a, const BigInt &b) {
    return a = a + b;
}

BigInt f[MAXN + 1], sum[MAXN + 1];

inline void makeTable() {
    for (int i = 1; i < 10; i++) f[C[i]] += 1;
    for (int i = 1; i <= MAXN; i++) {
        for (int j = 0; j < 10; j++) {
            if (i + C[j] <= MAXN) f[i + C[j]] += f[i];
        }
    }

    sum[2] = f[2];
    for (int i = 3; i <= MAXN; i++) sum[i] = sum[i - 1] + f[i];
}

int main() {
    makeTable();

    int n;
    while (~scanf("%d", &n)) {
        if (n == 0 || n == 1) puts("0");
        else if (n < 6) std::cout << sum[n] << std::endl;
        else std::cout << sum[n] + 1 << std::endl;
    }
    return 0;
}