1 条题解
-
1
#include<bits/stdc++.h> using namespace std; int main(){ int n,m; cin >> n; // 读入计分序列长度 vector<int> a(n + 1); // 计分序列,a[k]表示连续k个abc的得分 for(int i = 1;i <= n;i++){ cin >> a[i]; // 读入计分序列 } cin >> m; // 读入字符串长度 string s; cin >> s; // 读入字符串 // dp[i]表示前i个字符能获得的最大得分 vector<long long> dp(m + 1,0); for(int i = 0;i < m;i++){ // 不选取当前字符作为计分子串的开头,直接继承前一个状态 dp[i + 1] = max(dp[i + 1],dp[i]); // 检查从位置i开始是否是"abc" if(i + 2 < m && s.substr(i,3) == "abc"){ // 选取1个"abc",得分a[1] dp[i + 3] = max(dp[i + 3],dp[i] + a[1]); // 尝试选取连续多个"abc" int k = 1; // 当前已经匹配的"abc"个数 // 检查是否能继续匹配更多"abc" while(k < n && i + 3 * (k + 1) <= m && s.substr(i + 3 * k,3) == "abc"){ k++; // 增加匹配的"abc"个数 // 更新dp值,选取k个连续的"abc",得分a[k] dp[i + 3 * k] = max(dp[i + 3 * k],dp[i] + a[k]); } } } // 输出整个字符串的最大得分 cout << dp[m]; return 0; }
- 1
信息
- ID
- 779
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 显示难度暂无评定
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者