P2890 [USACO07OPEN]Cheapest Palindrome G

#include<bits/stdc++.h>
using namespace std;
class solve{
	public:
		int n,m;
		map < char , int > Map,Maps;
		char s[2222];
		int f[2222][2222];
		void main(){
			cin>>n>>m;
			scanf("%s",s+1);
			memset(f,0x3f3f3f3f,sizeof(f));
			for(int i=1; i<=n; i++)
			{
				char ch[1];
				int x,y;
				scanf("%s ",ch);
				scanf("%d%d",&x,&y);Map[ch[0]]=x;Maps[ch[0]]=y;
			}
			for(int i=1; i<=m; i++)f[i][i]=0;
			for(int len=1; len<m; len++)
			{
				for(int i=1; i+len<=m; i++)
				{
					int j=i+len;
					f[i][j]=min(f[i][j-1]+Maps[s[j]],f[i][j]);
					f[i][j]=min(f[i+1][j]+Maps[s[i]],f[i][j]);
					f[i][j]=min(f[i][j-1]+Map[s[j]],f[i][j]);
					f[i][j]=min(f[i+1][j]+Map[s[i]],f[i][j]);
					if(s[i]==s[j])
					{
						if(i==j-1)
						f[i][j]=0;
						else
						f[i][j]=min(f[i][j],f[i+1][j-1]);
					}
				}
			}
			cout<<f[1][m]<<endl;
		}
}x;
int main()
{
	x.main();
}