题解：P10721 [GESP202406 六级] 计算得分

Czming__ · 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;
}