简答题
偏难
#20024
划分字符串
划分字符串


答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 100005;
int n;
char s[N];
int a[N];
long long f[N];
int main() {
scanf("%d", &n);
scanf("%s", s + 1); // 字符串下标从1开始
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
// DP:f[i] = 前i个字符分割后的最大收益
for (int i = 1; i <= n; ++i) {
int mask = 0; // 位掩码,记录当前分段出现过的字符
// j向左枚举分段起点,区间 [j, i]
for (int j = i; j >= 1; --j) {
int cur_bit = 1 << (s[j] - 'a');
// 当前字符已在分段内,无法继续向左拓展
if (mask & cur_bit) break;
mask |= cur_bit;
// 分段长度 len = i - j + 1
int seg_len = i - j + 1;
f[i] = max(f[i], f[j - 1] + a[seg_len]);
}
}
printf("%lld\n", f[n]);
return 0;
}</pre>
这道题暂未补解析。