POJ 3280 Cheapest Palindrome

解法

区間dp
dp[i][j] = [i, j)をpalindromeにする最小コスト

ソースコード

int main()
{
    int m, n;
    string s;
    cin >> n >> m >> s;

    const int inf = ten(8);
    int cost[256];
    fill(cost, cost + 256, inf);
    while (n--)
    {
	char c;
	int add, del;
	cin >> c >> add >> del;
	cost[c] = min(add, del);
    }

    static int dp[2048][2048]; // [i, j)
    erep(i, m) erep(j, m)
	dp[i][j] = inf;

    rep(i, m)
    	dp[i][i] = dp[i][i + 1] = 0;

    rep(len, m)
    {
	for (int i = 0, j = len; j <= m; ++i, ++j)
	{
	    if (i > 0)
		chmin(dp[i - 1][j], dp[i][j] + cost[s[i - 1]]);
	    if (j < m)
		chmin(dp[i][j + 1], dp[i][j] + cost[s[j]]);
	    if (i > 0 && j < m && s[i - 1] == s[j])
		chmin(dp[i - 1][j + 1], dp[i][j]);		
	}
    }
    printf("%d\n", dp[0][m]);
}