首页 > 代码库 > 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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。