View Code of Problem 2913

#include<string.h>
#include<stdio.h>

#define min(a, b) (a) < (b)?(a):(b)

int main(){
	int N, M;
	char s[2005];
	int cost[30] = {0};
	int dp[2505][2505];
	memset(dp, 0, sizeof(dp));
	scanf("%d%d\n", &N, &M);
 	gets(s);
	for(int i = 0, k, j; i < N; i++){
		char d;
		scanf("%c%d%d", &d, &k, &j);
		getchar();
		cost[d - 'a'] = min(k, j);
	}
	for(int i = 1; i < M; i++)
		for(int j = 0, k = i; k < M; j++, k++)
			if(s[j] == s[k])
				dp[j][k] = dp[j+1][k-1];
			else
				dp[j][k] = min(dp[j+1][k]+cost[s[j]-'a'],dp[j][k-1]+cost[s[k]-'a']);
	printf("%d\n", dp[0][M-1]);
	return 0;
}