算法
(DP) $O(k\log n)$
我们可以用dp计算出每个 $i \% k$ 的最大得分(即遍历下标 $i, i+k, i+2k, \cdots 所能得到的最大得分)$,再把这些最大得分加起来就是答案。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::max;
using std::vector;
using std::string;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(3);
rep(i, 3) cin >> a[i];
string s;
cin >> s;
vector<int> ctoi(256);
ctoi['r'] = 2;
ctoi['c'] = 0;
ctoi['p'] = 1;
int ans = 0;
rep(i, k) {
vector<int> x;
for (int j = i; j < n; j += k) {
x.push_back(ctoi[s[j]]);
}
vector<int> dp(2);
// dp[0]: 当前这一轮赢能得到的最大得分,dp[1]: 当前这一轮输能得到的最大得分
int pre = -1;
for (int nx : x) {
vector<int> p(2);
// p[0]: 前一轮赢能得到的最大得分,p[1]: 前一轮输能得到的最大得分
swap(dp, p);
dp[0] = max(p[0], p[1]);
if (pre == nx) {
dp[1] = p[0] + a[nx];
}
else {
dp[1] = max(p[0], p[1]) + a[nx];
}
pre = nx;
}
ans += max(dp[0], dp[1]);
}
cout << ans << '\n';
return 0;
}