题解
区间DP
没想出来的我该去看脑科1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using namespace std;
typedef long long ll;
int n,m,add[30],rem[30],dp[2005][2005];
char s[2005],ord[3],is[2005][2005]={0};
void init(){
scanf("%d%d%s",&n,&m,s);
for(int i=0;i<n;i++){
scanf("%s",ord);
scanf("%d%d",&add[ord[0]-'a'],&rem[ord[0]-'a']);
}
for(int i=0;i<m;i++)
for(int j=0;j<m;j++)
dp[i][j]=(i<j)?INF:0;
}
void solve(){
for(int j=0;j<m;j++)
for(int i=0;i+j<m;i++)
if(s[i]==s[i+j])dp[i][i+j]=dp[i+1][i+j-1];
else{
dp[i][i+j]=min(dp[i+1][i+j]+rem[s[i]-'a'],
min(dp[i+1][i+j]+add[s[i]-'a'],
min(dp[i][i+j-1]+rem[s[i+j]-'a'],
dp[i][i+j-1]+add[s[i+j]-'a'])));
}
printf("%d\n",dp[0][m-1]);
}
int main(){
init();
solve();
return 0;
}