POJ 3280 Cheapest Palindrome

今では典型ですね。

問題

3280 -- Cheapest Palindrome

解法

典型なので略。

const int INF = 1e9;
int dp[2020][2020];
int cost[26][2];
string s;

int dfs(int l, int r) {
    if (l >= r) return 0;
    int& ret = dp[l][r];
    if (ret != -1) return ret;
    ret = INF;
    if (s[l] == s[r]) ret = min(ret, dfs(l+1, r-1));
    ret = min(ret, dfs(l+1, r) + cost[s[l]-'a'][1]);
    ret = min(ret, dfs(l, r-1) + cost[s[r]-'a'][1]);
    ret = min(ret, dfs(l, r-1) + cost[s[r]-'a'][0]);
    ret = min(ret, dfs(l+1, r) + cost[s[l]-'a'][0]);
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    cin >> s;
    for (int i = 0; i < 26; i++) for (int j = 0; j < 2; j++) cost[i][j] = INF;
    for (int i = 0; i < N; i++) {
        char c;
        int ic, dc;
        cin >> c >> ic >> dc;
        cost[c-'a'][0] = ic; cost[c-'a'][1] = dc;
    }
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, M-1) << endl;
    return 0;
}