题解

写在前面

dp[i]= 以i结尾的子串所能获得的最大价值。
dp[i]=max(dp[i],dp[j-1]+a[i-j+1])：当前子串所能获得的最大价值=之前存储的最大价值与当前子串之前的最大价值+当前子串所能获得的长度价值的较大值

使用二重循环解决。先循环i，代表以i结尾的子串；再循环j，代表当前子串为[j,i]。

使用二进制状态压缩，将每个字符出现形况用mask变量记录，第j位如果为1代表第j个字母以及出现在以i结尾的子串中。

注意，dp数组需要开long long。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

long long n,a[N],dp[N];
string s;

int main(){
	cin>>n>>s;
	s=" "+s;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	for(int i=1;i<=n;i++){
		int mask=0;
		
		for(int j=i;j>=1;j--){
			int cnt=1<<(s[j]-'a'); //将s[j]对应的字母映射到二进制对应位数中
			
			if(mask&cnt) break; //如果和之前出现过的字母重复，退出
			
			mask|=cnt; //更新mask
			dp[i]=max(dp[i],dp[j-1]+a[i-j+1]);
		}
	}
	
	cout<<dp[n];
	
	return 0;
}