https://www.acmicpc.net/problem/2216
같은 위치에 있는 문자를 비교하여 아래와 같이 점수를 받습니다.
1. 두 문자가 같은 경우에는 A(> 0)점을 받게 된다. 단, 두 문자가 모두 공백인 경우는 허용되지 않는다.
2. 두 문자 중 적어도 하나가 공백인 경우에는 B(< 0)점을 받게 된다.
3. 두 문자가 모두 공백이 아니고 서로 다른 경우에는 C(< 0)점을 받게 된다.
여기서 문자 사이에 공백을 원하는대로 넣을수 있기 때문에
적절하게 공백을 넣어서 점수를 최대로 받아야 하는 문제입니다.
dp[idx1][idx2]: 문자열을 idx1, idx2까지 사용했을 때 얻을 수 있는 최대 점수
s1, s2 중 하나의 문자에 공백을 추가하거나 두 문자를 비교하여 a, b, c 중 적절한 값을 더합니다.
위 3가지 중 max를 구하도록 합니다.
|
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
|
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#define MAX 3010
using namespace std;
string s1, s2;
int dp[MAX][MAX];
int a, b, c;
int len1, len2;
int solve(int idx1, int idx2) {
if (idx1 == len1) return (len2 - idx2) * b;
if (idx2 == len2) return (len1 - idx1) * b;
int& ret = dp[idx1][idx2];
if (ret != -1) return ret;
ret = b + max(solve(idx1 + 1, idx2), solve(idx1, idx2 + 1));
if (s1[idx1] == s2[idx2]) {
ret = max(ret, solve(idx1 + 1, idx2 + 1) + a);
}
else {
ret = max(ret, solve(idx1 + 1, idx2 + 1) + c);
}
return ret;
}
void func() {
memset(dp, -1, sizeof(dp));
cout << solve(0, 0) << '\n';
}
void input() {
cin >> a >> b >> c >> s1 >> s2;
len1 = s1.size();
len2 = s2.size();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 1229 육각수 (0) | 2024.06.30 |
|---|---|
| boj 25378 조약돌 (0) | 2024.06.29 |
| boj 1354 무한 수열 2 (0) | 2024.06.27 |
| boj 3114 사과와 바나나 (0) | 2024.06.13 |
| boj 11560 다항식 게임 (0) | 2024.06.13 |