BOJ)13330 유사 팰린드롬

문제: icpc.me/13330

w를 구성할 수 있는 세타 팰린드롬의 최소 개수를 출력하는 문제이다.

이 문제를 해결하기 위하여 두가지 디피 테이블을 정의해야한다.

dp1[l][r]은 l,r 구간의 u의 개수 

dp2[pos]는 0~pos 의 문자열을 구성 할 수 있는 세타 팰린드롬의 최소 개수라 정의하면

n^2으로 dp2를 채우기 위해 for문을 돌릴 때 이터레이터 j에 대한 검사를 dp1으로 할 수있다. 

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, k, l, dp[10010];
int a[10010][10010];
char s[10010];
int func(int l, int r) {
    if (l >= r)return 0;
    int &ret = a[l][r];
    if (ret != -1)return ret;
    if (s[l] != s[r])return 0;
    return ret = 1 + func(l + 1, r - 1);
}
int main() {
    scanf("%d%d%d", &n, &k, &l);
    scanf("%s", s + 1);
    memset(a, -1, sizeof(a));
    for (int i = 1; i <= n; i++)
        dp[i] = 1e9;
    for (int i = 1; i <= n; i++) {
        if (k*i <= 2 * l*func(1, i))dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (k*(i - j) <= 2 * l*func(j + 1, i))
                dp[i] = min(dp[i], dp[j] + 1);
        }
    }
    printf("%d\n", dp[n] == 1e9 ? 0 : dp[n]);
    return 0;
}