View Code of Problem 2913

#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.


Back to problem 2913