티스토리 뷰

알고리즘 관련/BOJ

BOJ)13330 유사 팰린드롬

JASON 자손9319 2017. 9. 8. 18:10

문제: icpc.me/13330


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


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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 = + func(l + 1, r - 1);
}
int main() {
    scanf("%d%d%d"&n, &k, &l);
    scanf("%s", s + 1);
    memset(a, -1sizeof(a));
    for (int i = 1; i <= n; i++)
        dp[i] = 1e9;
    for (int i = 1; i <= n; i++) {
        if (k*<= * l*func(1, i))dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (k*(i - j) <= * l*func(j + 1, i))
                dp[i] = min(dp[i], dp[j] + 1);
        }
    }
    printf("%d\n", dp[n] == 1e9 : dp[n]);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)5883 아이폰 9S  (0) 2017.10.13
BOJ)5542 JOI 국가의 행사  (0) 2017.09.12
BOJ)13330 유사 팰린드롬  (0) 2017.09.08
BOJ)13352 석양이 진다...  (1) 2017.09.07
BOJ)5842 Partitioning the Farm  (0) 2017.09.07
BOJ)2337 트리 자르기  (1) 2017.09.05
댓글
댓글쓰기 폼