Grime Zoo（思维/贪心）

题目 参考

题意：给定含?的01串，现在替换所有的？为0或1，要求替换后， 子 串 01 的 数 量 ∗ x + 子 串 10 的 数 量 ∗ y 子串01的数量 * x + 子串10的数量 * y 子串01的数量∗x+子串10的数量∗y最小。其中这里的子串可以是不连续的。

题解：考虑两个相邻的?，设其下标为l和r。设(l,r)区间中0的数量为 c 0 c_0 c0​，1的数量为 c 1 c_1 c1​。当我们在l，r分别填充0和1后，其贡献的代价总和 s u m 1 = ( c 1 + 1 + c 0 ) ∗ x + c o s t sum1 = (c_1+1+c_0)*x+cost sum1=(c1​+1+c0​)∗x+cost；当们在l，r分别填充1和0后，其代价总和 s u m 2 = ( c 0 + c 1 + 1 ) ∗ y + c o s t sum2=(c_0+c_1+1)*y+cost sum2=(c0​+c1​+1)∗y+cost。其中cost是l,r对于外界（左边界或右边界）所带来的贡献，由于此时0和1都分别贡献1次，因此代价是一样的。 又 s u m 1 − s u m 2 = ( x − y ) ∗ ( r − l ) sum1-sum2=(x-y)*(r-l) sum1−sum2=(x−y)∗(r−l)，可知，当x < y时，组合01会比10代价更小。根据此性质，我们知道，当x y也是类似的分析。

#include
using namespace std;
#define ll long long
const int maxn = 100010;

char s[maxn];
int x, y;

int pre[maxn], suf[maxn];
ll pre_sum[maxn], suf_sum[maxn];

int main() {
	scanf("%s", s + 1);
	scanf("%d%d", &x, &y);
	int n = strlen(s+1);
	
	if (x > y) {
		swap(x, y);
		for (int i = 1; i