题解 CF1443B 【Saving the City】
Suuon_Kanderu
2020-11-10 21:42:08
当成一个比较简单的线性 DP 入门题来做了。
首先 $dp_i$ 表示将前 i 个字符全部变为 0 的代价。
我们从前往后扫，遇到 `1` 时有两种选择：
1. 顺延最近的一个 A 操作（显然我们要从前面最近的一个 1 顺延），但我们需要把这两个 `1` 中间的 `0` 全部用 B 操作染色。
2. 另起炉灶，从这个位置开始，使用一个新的 A 操作。
还有一个注意事项，第一个 `1` 只能用一个 A 操作。
所以状态转移方程就出来了：
$$ dp_i = \begin{cases} dp_{i-1} &\text{if }(s_i = 0)\\dp_{k} + \min((i - k - 1)\cdot B , A) &\text{if }(s_i=1) \end{cases} $$
(P.S. $k$ 为 $i$ 前面最近的 1 的位置, $s$ 为字符串。)
```
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
string s;
int last = 0;
int dp[N];
void solve() {
int a , b;scanf("%d%d" , &a , &b);
cin >> s;
int last = 0 , i;
for(i = 0; i < s.size(); i++)
if(s[i] == '1')
{dp[i] = a; last = i;break;}
for(i++; i < s.size(); i++) {
if(s[i] == '0')dp[i] = dp[i - 1];
else {
dp[i] = dp[last] + min(a , (i - last - 1) * b);
last = i;
}
}
printf("%d\n" , dp[s.size() - 1]);
}
int main() {
int t;scanf("%d" , &t);
while(t--) {solve();}
}
```