by hansang:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
typedef long long LL;
char s[N]; LL f[N][N];
struct node{LL x, y, mn;} a[N];
int main(){
    int n, m; scanf("%d%d", &m, &n);
    scanf("%s", s + 1);
    for(int i = 1; i <= m; i++){
        char ss[5]; scanf("%s", ss);
        int t = ss[0] - 'a';
        scanf("%lld%lld", &a[t].x, &a[t].y);
        a[t].mn = min(a[t].x, a[t].y);
    }
    memset(f, 0x3f, sizeof(f));
    for(int i = n; i >= 1; i--){
        f[i][i] = 0;
        for(int j = i + 1; j <= n; j++){
            int t1 = s[i] - 'a', t2 = s[j] - 'a';
            f[i][j] = min(f[i+1][j] + a[t1].mn, f[i][j-1] + a[t2].mn);
            if(s[i] == s[j]){
                if(i + 1 == j) f[i][j] = 0;
                else f[i][j] = min(f[i][j], f[i+1][j-1]);
            }
        }
    }
    printf("%lld\n", f[1][n]);
    return 0;
}

by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
typedef long long LL;
char s[N]; LL f[N][N];
struct node{LL x, y, mn;} a[N];
int main(){
    int n, m; scanf("%d%d", &m, &n);
    scanf("%s", s+1);
    for(int i=1; i<=m; i++){
        char ss[5]; scanf("%s", ss);
        int t=ss[0]-'a';
        scanf("%lld%lld", &a[t].x, &a[t].y);
        a[t].mn=min(a[t].x, a[t].y);
    }
    memset(f, 0x3f, sizeof(f));
    for(int i=n; i>=1; i--){
        f[i][i]=0;
        for(int j=i+1; j<=n; j++){
            int t1=s[i]-'a', t2=s[j]-'a';
            f[i][j]=min(f[i+1][j]+a[t1].mn, f[i][j-1]+a[t2].mn);
            if(s[i]==s[j]){
                if(i+1==j) f[i][j]=0;
                else f[i][j]=min(f[i][j], f[i+1][j-1]);
            }
        }
    }
    printf("%lld\n", f[1][n]);
    return 0;
}