#include"iostream"
#include"vector"
#include"stdio.h"
using namespace std;
const int MAXN=2005;

vector<int> cost(30);

int GetMinCost(char* id,int M){
    vector< vector<int> > dp(MAXN,vector<int>(MAXN,0));

    for(int i=0;i<M;i++){
        for(int j=i-1;j>=0;j--){
            if(id[i]==id[j]){
                dp[i+1][j+1]=dp[i][j+2];
            }
            else{
                dp[i+1][j+1]=min(dp[i][j+1]+cost[id[i]-'a'],dp[i+1][j+2]+cost[id[j]-'a']);
            }
        }
    }

    return dp[M][1];
}

int main()
{
 //   freopen("in.txt","r",stdin);
    int N,M;
    char id[MAXN];
    while(scanf("%d%d",&N,&M)==2){
        cin>>id;
        int addCost,delCost;
        char ch;
        for(int i=0;i<N;i++){
            cin>>ch>>addCost>>delCost;
            cost[ch-'a']=min(addCost,delCost);
        }

        cout<<GetMinCost(id,M)<<endl;
    }
    return 0;
}

• Re:为什么会TLE (24) erwugumo 2021-03-25 16:27:32