区间$dp$

#include<bits/stdc++.h>
using namespace std;
char a[2005];
int n,m;
int del[2005],ins[2005];
long long dp[2005][2005];
int main()
{
	memset(dp,0x3f,sizeof(dp));
	cin>>n>>m;
	cin>>a+1;
	for(int i=1;i<=n;++i)
	{
		char x;
		cin>>x;
		cin>>ins[int(x)]>>del[int(x)];
		dp[i][i]=0;
	}
	dp[0][0]=0;
	for(int len=1;len<=m;++len)
	{
		for(int i=1,j=len+1;j<=m;++i,++j)
		{
			if(a[i]==a[j])
			{
				dp[i][j]=dp[i+1][j-1];
			}
			else
			{
				dp[i][j]=min(min(dp[i+1][j]+ins[a[i]],dp[i+1][j]+del[a[i]]),min(dp[i][j-1]+ins[a[j]],dp[i][j-1]+del[a[j]]));
			}
		}
	}
	cout<<dp[1][m]<<endl;
}