题目链接：便宜的回文串

这道题刚开始其实还是没有思路的.没办法，只能看题解了…

其实我们在思考问题时，考虑到一段串增或减时会改变它的长度，所以转移时会麻烦…

但其实不用考虑那么多的问题，我们只需记录下那一段子串需要变成回文串的最小代价，然后之后直接把它当成回文串用即可.

那这里我们就可以总结一些东西，也就是如果题目要求变成目标序列时，即使会改变原序列长度，但我们不用在意，照常做，用时直接把它当成合法序列即可.

那就是区间DP了，但这里还要注意一个性质，就是在一个串中，要把它变成回文串，删和减是等价的，例：abca，可以加成abcba也可以减成aca，都是对b进行处理的，我们加减都行，所以这道题给的两个代价，只需取个min就行.

之后的就没什么了…

#include
using namespace std;
int n,m,f[2100][2100];
char ch[2100];
mapmp;
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } int main() { freopen("1.in","r",stdin); n=read();m=read(); for(register int i=1;i<=m;++i) cin>>ch[i];
for(register int i=1;i<=n;++i) { char ch;cin>>ch;
int a=read(),b=read();
mp[ch]=min(a,b);
}
memset(f,127,sizeof(f));
for(register int i=1;i<=m;++i) f[i][i]=0;
for(register int len=2;len<=m;++len)
{
for(register int l=1;l<=m-len+1;++l)
{
int r=l+len-1;
if(ch[l]==ch[r])
{
if(len==2) f[l][r]=0;
else f[l][r]=f[l+1][r-1];
}
else
{
f[l][r]=min(f[l][r],f[l+1][r]+mp[ch[l]]);
f[l][r]=min(f[l][r],f[l][r-1]+mp[ch[r]]);
}
}
}
printf("%d",f[1][m]);
return 0;
}