2612번: DNA 유사도

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


$O(nm)$

lcs 비슷하게 풀면 된다.
문자열 s1[1...n], s2[1...m]이 주어졌을 때
dp[i][j]=부분 서열 s1[...i]과 s2[...j] 사이 최대 유사도
이 값은 다음 중 최댓값

1. s1[...i-1] + s1[i] / s2[...j-1] + s2[j]
-> dp[i-1][j-1] + (s1[i]==s2[j]이면 3 아니면 -2)
2. s1[...i] + ' ' / s2[...j-1] + s2[j]
-> dp[i][j-1]-2
3. s1[...i-1] + s1[i] / s2[...j] + ' '
-> dp[i-1][j]-2
4. s1[i] / s2[j] 즉, 시작지점
-> s1[i]==s2[j]이면 3 아니면 -2

dp 테이블 중 최댓값을 출력하고 시작지점을 찾아 부분서열을 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int l1, l2, dp[1001][1001], maxi, px, py;
pair<int, int> fr[1001][1001];
char s1[1002], s2[1002];
int main() {
    scanf("%d%s%d%s", &l1, s1 + 1, &l2, s2 + 1);
    for (int i = 1; i <= l1; i++) {
        for (int j = 1; j <= l2; j++) {
            if (s1[i] == s2[j]) dp[i][j] = 3, fr[i][j] = { i,j };
            int t = dp[i - 1][j - 1] + (s1[i] ^ s2[j] ? -2 : 3);
            if (dp[i][j] < t) {
                dp[i][j] = t;
                fr[i][j] = fr[i - 1][j - 1];
            }
            if (dp[i][j] < dp[i - 1][j] - 2) {
                dp[i][j] = dp[i - 1][j] - 2;
                fr[i][j] = fr[i - 1][j];
            }
            if (dp[i][j] < dp[i][j - 1] - 2) {
                dp[i][j] = dp[i][j - 1] - 2;
                fr[i][j] = fr[i][j - 1];
            }
            if (maxi < dp[i][j]) {
                maxi = dp[i][j];
                px = i; py = j;
            }
        }
    }
    s1[px + 1] = s2[py + 1] = 0;
    printf("%d\n%s\n%s", maxi, s1 + fr[px][py].first, s2 + fr[px][py].second);
    return 0;
}