백준 2216 - 문자열과 점수

icpc.me/2216

 

Solution.

다음 점화식을 고려하여 탑 다운 dp로 푼다.

 

dp[i][j] := 첫번째 문자열을 i개, 두번째 문자열을 j개 썼을 때 얻을 수 있는 최대 점수

 

이때 테이블의 초기화는 값이 겹치는 걸 방지하기 위해 아주 큰 값이나 아주 작은 값으로 초기화 한다.

 

전체 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
 
using namespace std;
 
int dp[3001][3001];
 
int a, b, c;
string u, d;
int ulen, dlen;
 
int memo(int ui, int di);
 
int main()
{
    fill(&dp[0][0], &dp[0][0] + 3001 * 3001, 1e9);
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> a >> b >> c >> u >> d;
 
    ulen = u.size(), dlen = d.size();
 
    cout << memo(0, 0);
}
 
int memo(int ui, int di)
{
    int &ret = dp[ui][di];
 
    if (ret != 1e9)
        return ret;
    
    ret = 0;
 
    if (ui == ulen && di == dlen)
        return ret;
 
    int tmp = -1e9;
 
    if (ui < ulen && di < dlen)
    {
        if (u[ui] == d[di])
            tmp = max(tmp, memo(ui + 1, di + 1) + a);
        else
            tmp = max(tmp, memo(ui + 1, di + 1) + c);
    }
 
    if (ui < ulen)
        tmp = max(tmp, memo(ui + 1, di) + b);
 
    if (di < dlen)
        tmp = max(tmp, memo(ui, di + 1) + b);
 
    return ret += tmp;
}