题解 | 竹摇清风拂面

#include <iostream>
using namespace std;

#include<vector>
#include<algorithm>
#include<string>
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
vector<long long>v(n);
for(int i=0;i<n;i++){
    cin>>v[i];
}
vector<vector<long long>> cost(n+1,vector<long long>(n+1,1e18));
for(int i=1;i<=n;i++){
    cost[i][i-1]=0;
}

for(long long len=2;len<=n;len+=2){
    for(int i=0;i+len-1<n;i++){
int j=i+len-1;
for(int k=i+1;k<=j;k+=2){
    if(s[k]==s[i]){
        if(cost[i+1][k-1]!=1e18&&cost[k+1][j]!=1e18){
            long long c=cost[i+1][k-1]+cost[k+1][j]+v[i]*v[k];
            cost[i][j]=min(c,cost[i][j]);
        }
    }
}

    }
}
if(cost[0][n-1]==1e18){
    cout<<-1<<endl;
}
else{
    cout<<cost[0][n-1]<<endl;
}

}


    return 0;
}