4632: 【GESP2406六级】计算得分

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

算由$m$ 个小写字母组成的字符串的得分。
小杨设置了一个包含$n$ 个正整数的计分序列 $A=[a_1,a_2,...,a_n]$，如果字符串的一个子串由$k$ ($1\le k\le n$ ) 个 abc 首尾相接组成，那么能够得到分数$a_k$ ，并且字符串包含的字符不能够重复计算得分，整个字符串的得分是计分子串的总和。
例如，假设$n=3$ ，字符串 dabcabcabcabzabc 的所有可能计分方式如下：
d+abc+abcabc+abz+abc 或者 d+abcabc+abc+abz+abc，其中 d 和 abz 不计算得分，总得分为$a_1+a_2+a_1$
d+abc+abc+abc+abz+abc，总得分为$a_1+a_1+a_1+a_1+a_1$
d+abcabcabc+abz+abc，总得分为$a_3+a_1$
小杨想知道对于给定的字符串，最大总得分是多少。

输入

第一行包含一个正整数$n$ ，代表计分序列$A$ 的长度。
第二行包含$n$ 个正整数，代表计分序列$A$ 。
第三行包含一个正整数$m$ ，代表字符串的长度。
第四行包含一个由$m$ 个小写字母组成的字符串。

输出

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

样例输入 复制 

3
3 1 2
13
dabcabcabcabz

样例输出 复制 

9

提示

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[30];
string s;
int dp[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int m;
    cin>>m;
    cin>>s;
    for(int i=1;i<=m;i++){
        dp[i]=dp[i-1];
        for(int j=1;j<=n;j++){
            if(i-3*j+1<=0)break;
            int l = i-3*j+1;
            if(s.substr(l-1,3)=="abc"){
                dp[i]=max(dp[i],dp[l]+a[j]);
            }else break;
        }
    }
    cout<<dp[m]<<"\n";
}

来源/分类

提交提交记录统计露一手!