题解

区间DP是普及-我吃
dp[i][j]:从i到j位的字符串变为回文串的最小花费，那么我们就可以得到转移方程：

dp[i][i+k]=min(dp[i][i+k],min(mp[i][i+k],dp[i][j]+dp[j+1][i+k]));
mp[i][j]表示不分割从i到j位的字符串变为回文串的花费

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;int n,a[10001],dp[2001][2001],mp[2001][2001],sum;
int f(int aa,int bb){
	int sum=0;
	for(int i=aa;i<=(aa+bb)/2;i++){
		if(s[i]!=s[bb-i+aa]){
			sum+=min(a[i],a[bb-i+aa]);
		}
	}return sum;	
}//计算不分割直接转成回文串的花费
signed main(){
	cin>>n>>s;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}for(int i=0;i<n;i+=2){
		for(int j=i+1;j<n;j+=2){
			dp[i][j]=INT_MAX;//初始化
			mp[i][j]=f(i,j);//用mp存储，放在下面的转移方程里会TLE
		}
	}for(int i=0;i<n;i++){
		if(i%2==0){
			dp[i][i+1]=mp[i][i+1];
		}
	}
	for(int k=3;k<n;k+=2){//k一定要是最外层的循环
		for(int i=0;i+k<n;i+=2){
			for(int j=i+1;j<i+k;j+=2){
				dp[i][i+k]=min(dp[i][i+k],min(mp[i][i+k],dp[i][j]+dp[j+1][i+k]));
			}
		}
	}cout<<dp[0][n-1]<<endl;
}