题解

传送门

一道略难的线性DP题目。

思路

逐个考虑以i结尾的子串，再逐个考虑当前以i结尾的子串是否包含由j个"abc".

状态定义：dp[i] = 以i结尾的某个子串的最大价值。

状态转移方程：

1. 当前的价值至少由为之前的最大价值，先继承。
2. 从小往大枚举当前以i结尾的子串有多少个"abc"。（因为是从前往后考虑，所以只须考虑子串开头的3个字符是否为"abc"即可，后面的元素如果不全为"abc"将不会进入当前循环。）
   1. 如果满足要求：在现在的dp[i]和当前满足要求子串开头之前的最大值dp[l-1]取大，作为以i结尾的最大值dp[i]。
   2. 如果不满足要求：之后的也不用再考虑了，此处已经出现了“断层”，break返回。

代码

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

int n,m,a[100],dp[N+10];
string s;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>m>>s;
	s=" "+s;
	
	for(int i=1;i<=m;i++){ //遍历每一个以 i 结尾的可能的子串
		dp[i]=dp[i-1]; //最差的情况：不考虑当前字符，只继承之前的最大值
		
		for(int j=1;j<=n;j++){ //逐个尝试可能个数的 abc
			if(i-3*j+1<=0) break;
			
			int l=i-3*j+1; //当前 abc 的个数为 j，因此这个由 j 个 abc 组成的子串的起始位置为 l
			
			if(s.substr(l,3)=="abc") dp[i]=max(dp[i],dp[l-1]+a[j]); //只须判断新的位于子串开头的三个字符是否为 abc，不为 abc 直接退出当前的循环
			else break;
		}
	} 
	
	cout<<dp[m];
	
	return 0;
}