题目链接

Cheapest Palindrome POJ - 3280

思路

$$ dp[i][j] 表示 串 \left( i, j\right)为回文串时的花费\\\\dp[i][j] 可以由dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] 转移到。 $$

时间复杂度

$$ O(M^2) $$

代码

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 2000 + 10;
const int INF = 0x3f3f3f3f;

char s[MAXN];
int dp[MAXN][MAXN];
int a[50], b[50];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);// don't forget &
    scanf("%s", s + 1);// no &

    for (int i = 1; i <= n; i++) {
        char c[5];
        scanf("%s", c);// no &
        scanf("%d%d", &a[c[0] - 'a'], &b[c[0] - 'a']);// don't forget &
    }

    for (int k = 2; k <= m; k++) {
        for (int i = 1; i + k - 1 <= m; i++) {
            int j = i + k - 1;
            int cur = INF;
            cur = min(cur, dp[i + 1][j] + min(a[s[i] - 'a'], b[s[i] - 'a']));
            cur = min(cur, dp[i][j - 1] + min(a[s[j] - 'a'], b[s[j] - 'a']));
            if (s[i] == s[j]) {
                cur = min(cur, dp[i + 1][j - 1]);
            }
            dp[i][j] = cur;
        }
    }

    printf("%d", dp[1][m]);
    return 0;
}