学步园

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define inf 0x7fffffff

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x*f;
}

int n, m, c[27], a[2001], f[2001][2001];
char s[2001];

int main() {
    n = read();
    m = read();
    scanf("%s", s);
    for (int i = 1; i <= m; i++)
        a[i] = s[i - 1] - 'a' + 1;
    for (int i = 1; i <= n; i++) {
        char ch[2];
        scanf("%s", ch);int a=read(),b=read();
        c[ch[0] - 'a' + 1] = min(a,b);
    }
    for (int j = 1; j <= m; j++)
        for (int i = j - 1; i >= 1; i--)
            if (a[i] == a[j])f[i][j] = f[i + 1][j - 1];
            else f[i][j] = min(c[a[i]] + f[i + 1][j], f[i][j - 1] + c[a[j]]);
    printf("%d", f[1][m]);
    return 0;
}