UVA10721 - Bar Codes(DP)
제목 링크
제목 대의: n,k,m를 주고 BC(n,k,m)bar 코드의 수를 충족시켜야 합니다.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
", DP(1, 1, 1));
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
