红路灯!
查看原帖
红路灯!
1674226
markwu1楼主2025/7/26 10:45
#include<bits/stdc++.h>
using namespace std;
long long m=0;
long long n=0;
long long a[33358]={0};
long long dp[100008]={0};
vector<int> end_;
vector<int> space;
string s="";
int find_last_abc(int z){
	for(int i=end_.size()-1;i>=0;i--){
		if(end_[i]<space[z]){
			return i;
		}
	}
	return 0;
}
long long f(int cut){
	for(int i=find_last_abc(cut)+1;i<=find_last_abc(cut+1);i++){
		dp[end_[i]]=a[1];
		for(int j=i-1;j>=0 && end_[j]>space[cut];j--){
		//	cout<<j;
			dp[end_[i]]=max(dp[end_[i]],dp[end_[j]]+a[i-j]);
			//cout<<j<<' '<<calc(j+1,i)<<endl;
		}
	//	cout<<end_[i]<<' '<<dp[end_[i]]<<endl<<endl;
	}
	return dp[end_[find_last_abc(cut+1)]];
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cin>>m>>s;
	for(int i=n+1;i<=ceil(m/3);i++){
		a[i]=(-33333008);
	}
	s=s+"dabc";
	end_.push_back(0);
	space.push_back(-1);
	for(int i=0;i<=m;i++){
		if(i>=2){
			if(s[i]=='c' && s[i-1]=='b' && s[i-2]=='a'){
				end_.push_back(i);
			}
			else if(s[i+3]=='c' && s[i+2]=='b' && s[i+1]=='a'){
				space.push_back(i);
			}
		}
		else if(s[i+3]=='c' && s[i+2]=='b' && s[i+1]=='a'){
			space.push_back(i);
		}
	}
	long long ans=0;
	for(int i=1;i<space.size()-1;i++){
		ans=ans+f(i);
	//	cout<<ans<<' ';
	}
	cout<<ans;
	return 0;
}
2025/7/26 10:45
加载中...