P2890 [USACO07OPEN]Cheapest Palindrome G

#include <bits/stdc++.h>
using namespace std;
char li[3001];
char tmp[3];
int cst[28];
long long ans[3001][3001];
int main(){
	int n,len;cin>>n>>len;
	scanf("%s",li+1);
	for(int i=1;i<=len;i++){
		li[i]=li[i]-'a'+1;
	}
	for(int i=1;i<=n;i++){
		scanf("%s",tmp+1);int tmp2,tmp3;cin>>tmp2>>tmp3;
		cst[tmp[1]-'a'+1]=min(tmp2,tmp3);
	}
	for(int cd=2;cd<=len;cd++){
		for(int u=1;u+cd-1<=len;u++){
			int v=u+cd-1;
			ans[u][v]=min(ans[u][v-1]+cst[(int)li[v]],ans[u+1][v]+cst[(int)li[u]]);
			if(li[u]==li[v])ans[u][v]=min(ans[u+1][v-1],ans[u][v]);
		}
	}
	cout<<ans[1][len];
}