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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include <stdio.h> #include <cstring> #include <algorithm> using namespace std; int dp[1001][1001] = { 0 }; char a[1001], b[1001], result[1001] = { 0 }; int main() { scanf("%s %s", &a, &b); getchar(); int n = strlen(a); int m = strlen(b); for (int i = 0; i <= n; i++) { dp[0][i] = 0; } for (int i = 0; i <= m; i++) { dp[i][0] = 0; } for (int j = 0; j < m; j++) { for (int i = 0; i < n; i++) { if (a[i] == b[j]) { dp[j + 1][i + 1] = dp[j][i] + 1; } else { dp[j + 1][i + 1] = max(dp[j][i + 1], dp[j + 1][i]); } } } int idx = 0,st=n-1; for (int j = m; j >=0; j--) { int snum = dp[j][st]; for (int i =st-1; i >=0; i--) { if (dp[j][i] != snum) { result[idx++] = a[i]; st = i; break; } } } for (int i = idx-1; i >=0; i--) { printf("%c", result[i]); } printf("%d", dp[m][n]); } | cs |
'알고리즘 > DP' 카테고리의 다른 글
돌다리건너기 더블릿 (2602 백준) (0) | 2019.02.10 |
---|---|
부분합 더블릿 (0) | 2019.02.09 |
1149 RGB거리 (0) | 2019.02.09 |
1463 1로 만들기 (0) | 2019.02.08 |
2600 구슬게임 (0) | 2019.02.08 |