gesp(C++六级)（9）洛谷：P10721：[GESP202406 六级] 计算得分

gesp(C++六级)（9）洛谷：P10721：[GESP202406 六级] 计算得分

题目描述

小杨想要计算由 $m$ 个小写字母组成的字符串的得分。

小杨设置了一个包含 $n$ 个正整数的计分序列 $A=[a_1,a_2,\dots ,a_n]$，如果字符串的一个子串由 $k(1\le k\le n)$ 个 $\text{abc}$ 首尾相接组成，那么能够得到分数 $a_k$，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。

例如，假设 ，字符串 $\text{dabcabcabcabzabc}$ 的所有可能计分方式如下：

• $\text{d+abc+abcabc+abz+abc}$ 或者 $\text{d+abcabc+abc+abz+abc}$，其中 $\text{d}$ 和 $\text{abz}$ 不计算得分，总得分为 $a_1+a_2+a_1$。
• $\text{d+abc+abc+abc+abz+abc}$，总得分为 $a_1+a_1+a_1+a_1$。
• $\text{d+abcabcabc+abz+abc}$，总得分为 $a_3+a_1$。

小杨想知道对于给定的字符串，最大总得分是多少。

输入格式

• 第一行包含一个正整数 $n$，代表计分序列 $A$ 的长度。

• 第二行包含 $n$ 个正整数，代表计分序列 $A$。

• 第三行包含一个正整数 $m$，代表字符串的长度。

• 第四行包含一个由 $m$ 个小写字母组成的字符串。

输出格式

输出一个整数，代表给定字符串的最大总得分。

样例 #1

样例输入 #1

3
3 1 2
13
dabcabcabcabz

样例输出 #1

9

提示

样例解释

最优的计分方式为 $\text{d+abc+abc+abc+abz}$，总得分为 $a_1+a_1+a_1$，共 $9$ 分。

数据范围

对于全部数据，保证有 $1\le n\le 20$，$1\le m\le 10^5$，$1\le a_i\le 1000$。

AC代码（100分）

#include<bits/stdc++.h>
using namespace std;
/*思路： 
	动态规划：
	1、dp[i]含义：以第i个字符结尾的最大总得分 
	2、状态转移方程：
	   dp[i]=max(dp[i],dp[i-3*j]+a[j])；
	   备注1：j表示连续"abc"的个数
	   备注2：需满足条件i>=3*j，避免数组越界
	   备注3：a[j]表示j个abc首尾相接能够得到的分数 
*/
int n,m,a[30],dp[100010]; 
string s;
//判断函数:判断子串是不是连续的abc首尾相接 
bool check(string s){
	for(int i=2;i<s.size();i+=3){
		if(s.substr(i-2,3)!="abc") return false;
	}
	return true;
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>m;
	cin>>s;
	//dp 
	for(int i=3;i<=m;i++){//枚举字符串的结尾字符（以1、2结尾没意义：不可能构成"abc"） 
		dp[i]=dp[i-1];//dp[i]初始化 
		for(int j=1;j<=n;j++){//枚举"abc"首尾相接的个数，题目给定的最多n个 
			if(i>=3*j){
				string s2=s.substr(i-3*j,3*j);//截取子串，长度为3*j 
				if(check(s2)){//如果长度为3*j的子串s2是j个连续的"abc"串 
					dp[i]=max(dp[i],dp[i-3*j]+a[j]);//状态转移方程 
				} 
			}
		}
	}
	//输出答案
	cout<<dp[m]; 
	return 0;
}

文末彩蛋：

点击王老师青少年编程主页有更多精彩内容