#include <iostream> #include <cstdio> #include <cstring> #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; const int MAXN = 2005; const int INF = 0x3f3f3f3f; int n, m; char str[MAXN]; int val[26]; int dp[MAXN][MAXN]; int main(void) { while (~scanf("%d%d", &n, &m)) { char tmp; scanf("%s", str); for (int i = 0; i < n; i++) { getchar(); scanf("%c", &tmp); int a, d; scanf("%d%d", &a, &d); val[tmp - 'a'] = Min(a, d); } memset(dp, 0, sizeof dp); int lim = strlen(str); //从讨论长度为1的子串开始,逐渐加长子串的长度 for (int len = 1; len < lim; len++) { for (int i = 0, j = len; j < lim; i++, j++) { dp[i][j] = INF; if (str[i] == str[j]) dp[i][j] = dp[i + 1][j - 1]; else dp[i][j] = Min(Min(dp[i][j], dp[i][j - 1] + val[str[j] - 'a']), Min(dp[i][j], dp[i + 1][j] + val[str[i] - 'a'])); } } printf("%d\n", dp[0][lim - 1]); } return 0; } |
Double click to view unformatted code.