题解
计算
4 条题解
-
0
#include<bits/stdc++.h> using namespace std; int n, m, a[40004], sum; // n:计分规则数量, m:字符串长度 string s; // 存储输入字符串 int main() { // 第一部分:输入处理 cin >> n; // 读取计分规则,a[k]表示k个连续"abc"的得分 for(int i = 1; i <= n; i++) cin >> a[i]; // 第二部分:动态规划预处理 // 预处理所有可能的连续"abc"组合得分(类似完全背包问题) // 这里假设最多40003个连续"abc"(可根据题目调整) for(int i = 1; i <= 40003; i++) // 枚举所有可能的分割点j(限制在n范围内优化性能) for(int j = 1; j <= min(i/2, n); j++)//只判断前一半比如1和9, 9和1是一样的 // 状态转移:a[i]取当前值或分割为j和i-j的和的最大值 a[i] = max(a[i], a[i-j] + a[j]); // 第三部分:字符串处理 cin >> m >> s; int x = 0; // 计数器,记录当前连续"abc"的数量 // 遍历字符串寻找连续的"abc"模式 for(int i = 0; i < m; i++) { // 检查当前位置是否构成"abc"模式 if(i+2 < m && s[i] == 'a' && s[i+1] == 'b' && s[i+2] == 'c') { x++; // 增加连续计数 i += 2; // 跳过已匹配的字符 } else { sum += a[x]; // 将当前连续数的得分加入总和 x = 0; // 重置计数器 } } // 处理最后一段可能剩余的连续"abc" sum += a[x]; // 输出最终得分 cout << sum; return 0; }
- 1