C. Save the Magazines
Monocarp has been collecting rare magazines for quite a while, and now he has decided to sell them. He distributed the magazines between $n$ boxes, arranged in a row. The $i$-th box contains $a_i$ magazines. Some of the boxes are covered with lids, others are not.
Suddenly it started to rain, and now Monocarp has to save as many magazines from the rain as possible. To do this, he can move the lids between boxes as follows: if the i-th box was covered with a lid initially, he can either move the lid from the i-th box to the box $(i−1)$ (if it exists), or keep the lid on the $i$-th box. You may assume that Monocarp can move the lids instantly at the same moment, and no lid can be moved more than once. If a box will be covered with a lid after Monocarp moves the lids, the magazines in it will be safe from the rain; otherwise they will soak.
You have to calculate the maximum number of magazines Monocarp can save from the rain.
Input
The first line contains a single integer $t$ $(1 \leq t \leq {10}^{4})$ — the number of the testcases.
The first line of each testcase contains a single integer $n$ $(1 \leq n \leq 2 \cdot {10}^{5})$ — the number of boxes.
The second line contains a string of $n$ characters $0$ and/or $1$. If the $i$-th character is $1$, the $i$-th box is initially covered with a lid. If the $i$-th character is $0$, the $i$-th box is initially not covered.
The third line contains a sequence of integers $a_1,a_2, \dots ,a_n$ $(1 \leq a_i \leq {10}^{4})$, where $a_i$ is the number of magazines in the $i$-th box.
The sum of n over all testcases doesn’t exceed $2 \cdot {10}^{5}$.
Output
For each testcase, print one integer — the maximum number of magazines Monocarp can save from the rain.
Example
input
4 5 01110 10 5 8 9 6 6 011011 20 10 9 30 20 19 4 0000 100 100 100 100 4 0111 5 4 5 1
output
27 80 0 14
Note
In the first testcase of the example, Monocarp can move the lid from the second box to the first box, so the boxes $1$, $3$ and $4$ are covered, and $10+8+9=27$ magazines are saved.
In the second testcase, Monocarp can move the lid from the second box to the first box, then from the third box to the second box, then from the fifth box to the fourth box, and then from the sixth box to the fifth box. The boxes $1, 2, 4$ and $5$ will be covered, so $20+10+30+20=80$ magazines can be saved.
There are no lids in the third testcase, so it’s impossible to save even a single magazine.
解题思路
比赛的时候是用dp做的。
定义状态$f(i, 0)$和$f(i, 1)$，其中$f(i, 0)$表示所有将前$i$个箱子的盖子移动完且第$i$个箱子没有使用第$i+1$个箱子的盖子的所有方案，$f(i, 1)$表示所有将前$i$个箱子的盖子移动完且第$i$个箱子使用第$i+1$个箱子的盖子的所有方案。属性就是保护的杂志的最大数量。
状态转移方程需要分类讨论：
- 第$i$个箱子原本没有盖子，且第$i+1$个箱子也没有盖子，那么有$f(i, 0) = f(i – 1, 0)$。
- 第$i$个箱子原本有盖子，且第$i+1$个箱子没有盖子，那么有$f(i, 0) = max\{ {f(i – 1, 0) + a_i, f(i – 1, 1)} \}$。
- 第$i$个箱子原本没有盖子，且第$i+1$个箱子有盖子，那么有$f(i, 0) = f(i – 1, 0),~ f(i, 1) = f(i – 1, 0) + a_i$。
- 第$i$个箱子原本有盖子，且第$i+1$个箱子有盖子，那么有$f(i, 0) = max\{ {f(i – 1, 0) + a_i, f(i – 1, 1)} \},~ f(i, 1) = f(i – 1, 1) + a_i$。
AC代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 2e5 + 10; 5 6 char s[N]; 7 int a[N]; 8 int f[N][2]; 9 10 void solve() { 11 int n; 12 scanf("%d %s", &n, s + 1); 13 for (int i = 1; i <= n; i++) { 14 scanf("%d", a + i); 15 } 16 17 memset(f, -0x3f, sizeof(f)); 18 f[0][0] = 0; 19 for (int i = 1; i <= n; i++) { 20 if (s[i] == '0' && s[i + 1] == 0) f[i][0] = f[i - 1][0]; 21 else if (s[i] == '1' && s[i + 1] == 0) f[i][0] = max(f[i - 1][0] + a[i], f[i - 1][1]); 22 else if (s[i] == '0' && s[i + 1]) f[i][0] = f[i - 1][0], f[i][1] = f[i - 1][0] + a[i]; 23 else f[i][0] = max(f[i - 1][0] + a[i], f[i - 1][1]), f[i][1] = f[i - 1][1] + a[i]; 24 } 25 printf("%d\n", f[n][0]); 26 } 27 28 int main() { 29 int t; 30 scanf("%d", &t); 31 while (t--) { 32 solve(); 33 } 34 35 return 0; 36 }
还可以用贪心。
我们将$s$序列分成若干段，每一段的形式都是第一个数是$0$，后面都是连续的$1$（可能只有一个$0$而没有$1$）。如果$s[0]$不为$0$，那么第一段就只包含连续的$1$。比如有$111010011$，那么按照这个规则$s$划分成如下形式：$[111]~[01]~[0]~[011]$。
为什么会想到这样子划分呢？因为根据题目的信息，每个盖子只能被移动一次，这样划分就可以保证每一段之间都是相互独立的，因为每一段的第一个位置为$0$（第一段除外），因此如果这个$0$被这一段后面的盖子覆盖后，由于这个盖子已经移动过一次了，因此不可能再往前移动，因此每一段都是互不影响的。
因此要求出所有箱子能保护的杂志最大数量，等价于求每一段中能够保存的杂志最大数量。可以发现对于 0 1 1 … 1 这种形式，通过往前移动盖子我们可以让$0$出现在任意一个位置，因此要使得这段中能保护的杂志数量最大，就是累加这一段中所有箱子存放的杂志数量，再减去存放最小杂志数量的箱子所存放的杂志（也就是说把$0$变到存放杂志数量最少的箱子上）。
为了方便，一开始就给序列$s$头插一个$0$，保证$s[0] = 0$。
AC代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 2e5 + 10; 5 6 char s[N]; 7 int a[N]; 8 9 void solve() { 10 int n; 11 scanf("%d %s", &n, s + 1); 12 s[0] = '0'; 13 for (int i = 1; i <= n; i++) { 14 scanf("%d", a + i); 15 } 16 17 int ret = 0; 18 for (int i = 0; i <= n; i++) { 19 if (s[i] == '0') { // 找到连续的1 20 int j = i + 1; 21 int sum = a[i], minv = a[i]; 22 while (j <= n && s[j] == '1') { 23 sum += a[j]; 24 minv = min(minv, a[j]); 25 j++; 26 } 27 ret += sum - minv; // 这一段的杂志总和减去最小的杂志数量，就是这一段能保存的最大杂志数量 28 i = j - 1; 29 } 30 } 31 printf("%d\n", ret); 32 } 33 34 int main() { 35 int t; 36 scanf("%d", &t); 37 while (t--) { 38 solve(); 39 } 40 41 return 0; 42 }
参考资料
Educational Codeforces Round 137 (Rated for Div. 2) A~E：https://zhuanlan.zhihu.com/p/574625054
原文地址：http://www.cnblogs.com/onlyblues/p/16815066.html
