这是我发的第一条帖子，点个赞让我到题解仙人吧！！ @看什么看看什么看看什么看看什么看 @AC君

@看什么看看什么看看什么看看什么看 变量未初始化 应该： 状态机逻辑混乱 * 当遇到非abc字符时，重置逻辑不完整 * last状态转换有问题，无法正确处理"abcabc"连续情况 * 比如遇到'b'时，如果last不是'a'，你的代码会记录cnt，但此时cnt可能为0 cnt计数错误 * 只有在遇到'c'时才++cnt，但应该每完成一个"abc"就计数 * 当连续"abc"中断时，重置逻辑有问题 边界情况处理缺失 * 字符串以"ab"结尾时，cnt不会被记录 * 遇到非连续字符时，状态重置不彻底 输入："abcabcx" 你的状态机可能无法正确识别这是2个连续的"abc"

@看什么看看什么看看什么看看什么看

传送门 一道略难的线性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; long long n,a[105],m; string s; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } cin>>m>>s; long long sum=0,ans=0; for(int i=0;i<s.size()-2;i++){ if(s[i]'a'&&s[i+1]'b'&&s[i+2]=='c'){ i+=2; ans++; }else{ long long dp[100005]; for(int j=1;j<=ans;j++){ for(int k=j;k<=ans;k++){//完全背包 dp[k]=max(dp[k],dp[k-j]+a[j]); } } sum+=dp[ans]; ans=0; } } long long dp[100005]; for(int j=1;j<=ans;j++){//防止最后三个数是'a''b''c'但还未算 for(int k=j;k<=ans;k++){ dp[k]=max(dp[k],dp[k-j]+a[j]); } } cout<<sum+dp[ans]; }