http://poj.org/problem?id=3280

由于在回文串一侧增加/删除一个字符等价于在另一侧删除/增加一个字符,所以对每个字符我们只取其最小花费。
要特别注意遍历顺序:倒着遍历左端点,正着遍历右端点。

/*16ms,14020KB*/

const int mx = 2005;

char s[mx];
int dp[mx][mx], cost[30];

int main()
{
    int n, m, a, b, i, j;
    char c;
    SII(n, m), getchar();
    gets(s);
    while (n--)
    {
        c = getchar(), SII(a, b), getchar();
        cost[c & 31] = min(a, b);
    }
    rFor(i, m - 2) Forr(j, i + 1, m)
        dp[i][j] = (s[i] == s[j] ? dp[i + 1][j - 1] : 
                    min(dp[i + 1][j] + cost[s[i] & 31], dp[i][j - 1] + cost[s[j] & 31]));
    PI(dp[0][m - 1]);
    return 0;
}

Comments

comments powered by Disqus