Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int OO=1e9;

int f[111][1111][33];
int a[33][33];
char s[1111];
bool v[111][1111][33];
int k;

int main()
{
    int n;
    char x,y;
    int c;
    memset(a,0,sizeof(a));
    memset(f,0,sizeof(f));
    memset(v,0,sizeof(v));
    // nhap s, k
    cin>>(s+1)>>k;
    // nhap n
    cin>>n;
    // duyet n lan de nhap x, y, c
    for (int i=1; i<=n; i++)
    {
        // nhap x, y, c
        cin>>x>>y>>c;
        // chi so a luu x, y; gia tri a luu c
        a[x-'a'][y-'a']=c;
    }
    // len luu chieu dai chuoi s
    int len=strlen(s+1);

    // mang 3 chieu:
    // chieu 1: duyet k ki tu thay doi
    // chieu 2: duyet chieu dai ki tu s
    // chieu 3: duyet mang ki tu
    for (int i=0;i<=len;i++)
    {
        for (int j=0;j<26;j++)
        {
            for (int l=0;l<=k;l++)
            {
                f[l][i][j]=-OO;
            }
        }
    }

    // duyet mang chu cai
    for (int i=0;i<26;i++)
    {
        // neu ki tu thu 2 cach a == i
        if (s[1]-'a'==i)
        {
            // khong ki tu nao thay doi
            // 1 ki tu thay doi
            // duyet mang chu cai
            f[0][1][i]=0;
        }
        else
        {
            // 1 ki tu thay doi

            f[1][1][i]=0;
        }
    }

    for (int i=2; i<=len; i++)
    {
        for (int j=0; j<26; j++)
        {
            if (j==s[i]-'a')
            {
                for (int l=0; l<=k; l++)
                    for (int t=0; t<26; t++)
                    {
                        f[l][i][j]=max( f[l][i][j], f[l][i-1][t]+a[t][j] );
                    }

            }
            else
            {
                for (int l=1; l<=k; l++)
                    for (int t=0; t<26; t++)
                    {
                        f[l][i][j]=max( f[l][i][j], f[l-1][i-1][t]+a[t][j] );
                    }
            }
        }
    }

    // tim max
    int ans=-OO;
    for (int l=0; l<=k; l++)
    {
        for (int j=0; j<26; j++)
        {
            if (f[l][len][j]>ans) ans=f[l][len][j];
        }
    }
    cout<<ans<<endl;

    return 0;
}