自动搬运

查看原文

来自洛谷，原作者为

	Czming__ 顺其自然，不如听其自然

搬运于2025-08-24 23:00:37，当前版本为作者最后更新于2024-07-10 11:40:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

很简单，就是说让你将一个字符串分割成几个小字符串（不重复），如果这个字符串是由 $k$ 个 $\texttt{abc}$ 首尾相接组成，就可以获得 $a_k$ 分（$1 \le k \le n$），问你最多能得几分。

题目转换

那么，我们以样例为例，那么是不是我们有且只有 $3$ 个连续的 $\texttt{abc}$？所以说，让 $\texttt{abcabcabc}$ 得分最大化，才是最后的目标。

所以说，这个 $\texttt{abc}$ 连续的数量你是无法改变，所以此题中，我们应该要让收益最大化。

所以说，这道题的正解应该是 dp 和字符串的基本操作，这题就容易了一些。

基本框架

• 打好一张 dp 表，$dp_k$ 表示 $k$ 个 $\texttt{abc}$ 最多可以得到几分（请思考，这道题是一道完全背包还是 $01$ 背包？）

• 然后在字符串中查询，其实就是一道最长平台，这里不重点展开。

就这样了，代码（注释并没有很多，但明白了思路，代码其实也不用）：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[21],dp[33334],sum;
string s;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=i;j<=33333;j++){
			dp[j]=max(dp[j],dp[j-i]+a[i]);
		}
	}//输入+完全背包。
	int i=0,k=0;
	cin>>m>>s;
	s=s+"#  ";//特例：abc:如果这句没有，那么就要最后算。 
	while(i<=m){
		if(s[i]=='a'&&s[i+1]=='b'&&s[i+2]=='c'){
			i+=3;
			k++;
		}
		else{
			i++;
			sum+=dp[k];
			k=0; 
		}
	}//find "abc" 并且加分。
	cout<<sum;
	return 0;
}