13330번: Palindromic

https://www.acmicpc.net/problem/13330

동적계획법을 이용해 해결할 수 있다.

s[i]: i번째 문자
lp[i][j]: s[j-i+1 ... j-i+1+k]와 s[j ... j-k]가 같은 최대 k
dp[i]: s[1...i]을 θ-팰린드롬 문자열들을 연결하여 만들 때 필요한 최소 문자열 수
자세한 구현은 다음 소스를 참고하자.


시간복잡도는 $O(n^2)$

#include<cstdio>
#include<algorithm>
using namespace std;
int lp[10001][10001], n, k, l, dp[10001];
char s[10002];
int main() {
    scanf("%d%d%d%s", &n, &k, &l, s + 1);
    for (int i = 2; i <= n; i++) for (int j = i; j <= n; j++) if (s[j - i + 1] == s[j]) lp[i][j] = lp[i - 2][j - 1] + 1;
    for (int i = 1; i <= n; i++) {
        dp[i] = n;
        for (int j = 2; j <= i; j++) if (2 * lp[j][i] * l >= j*k) dp[i] = min(dp[i], dp[i - j] + 1);
    }
    printf("%d", dp[n] < n ? dp[n] : 0);
    return 0;
}