首页 > 代码库 > UVA10721 - Bar Codes(DP)

UVA10721 - Bar Codes(DP)

UVA10721 - Bar Codes(DP)

题目链接

题目大意:给你n, k, m, 要求满足BC(n,k,m)bar code的数目。n表示这样的字符串长度为n,k表示相同颜色的段落有k段,m代表每段内最多只能有m个相同的。

解题思路:f[n][k][m]:表示第i个位置的字符,现在已经形成了k段,长度为m。
f[n][k][m] = f[n + 1][k][m + 1] + f[n + 1][k + 1][1];

代码:

#include <cstdio>
#include <cstring>

const int maxn = 55;

typedef long long ll;
int N, K, M;
ll dp[maxn][maxn][maxn];

void init () {

    memset (dp, -1, sizeof (dp));
}

ll DP (int n, int k, int m) {

    ll& ans = dp[n][k][m];
    if (ans != -1)
        return ans;
    if (n == N) {
        if (k == K)
            return ans = 1;
        return ans = 0;
    }

    ans = 0;
    if (k < K)
        ans += DP(n + 1, k + 1, 1);

    if (m < M)
        ans += DP(n + 1, k, m + 1);
    return ans;
}

int main () {

    while (scanf ("%d%d%d", &N, &K, &M) != EOF) {

        init();
        printf ("%lld\n", DP(1, 1, 1));
    }
    return 0;
}

UVA10721 - Bar Codes(DP)