题解
题面描述
给定一个长度为 n 的数组 a 以及一个长度为 n 的仅由字符 ′0′ 和 ′1′ 组成的字符串 s。每个位置 i 对应一个操作符：
- 若 si=′1′，则 op(i)=1；
- 若 si=′0′，则 op(i)=−1。
我们可以将数组切分为至多 k 块（也就是最多有 k−1 个切割点）。对于数组中每个位置 i，若其所在块的编号为 j（块的编号从 1 开始），则该位置的贡献为
P2708.第2题-字符串数组
题目内容
小红有一个长度为n的数组a和一个度为n的字符串s。她最多可以将数组切割成1块。
定义数组的权值为所有元素的权值之和。对于数组中的第1个元素，其权值计算方式为：op(i)×(a+j)
op(i)的值取决手字符串s的第i个字符:
-
若si='1'，则op(i)=1
-
若si='0’，则op(i)=−1
-
j表示ai所在的块的编号(从1开始)
小红想要通过合理的切割方式，使得数组的总权值最大，请你帮她计算出可能的最大权值。
输入描述
第一行包含两个正整数n和k，表示数组的长度和数组最多的块数。
第二行包含n个整数a1,a2，...an，表示数组a
第三行包含一个长度为n的字符串s，仅由字符‘0’和'1'组成
1≦k≦n
2≤n≤105
1≤ai≤109
输出描述
输出一个整数。表示数组可能的最大权值。
样例1
输入
4 2
1 2 3 4
1001
输出
1
说明
一种最优的切割方案是将数组切成[1,2,3]和[4]两块。
