题意

给出一个包含 0 1 ? 0 1 ? 0 1 ? 的序列 每个子序列 01 01 01会增加 x x x点愤怒值，每个子序列 10 10 10会增加 y y y点愤怒值

用 0 1 0 1 0 1代替所有的 ? ? ? 使得最终的愤怒值最小

思路

先用 1 1 1 代替所有的 ? ? ? 求出每个位置前缀和后缀中 1 0 ? 1 0 ? 1 0 ? 的数量 计算得到当前愤怒值 $re

如果 x < y x < y x<y 贪心地使得 01 01 01 多 10 10 10 少 即从前往后地将 ? ? ? 用 0 0 0 替换 遍历每种情况 求最小值

如果 x > y x > y x>y 贪心地使得 10 10 10 多 01 01 01 少 即从后往前地将 ? ? ? 用 1 1 1 替换 遍历每种情况 求最小值

p s : ps: ps: 在求最小值的过程中 刚开始我用

int x = vec[i];

导致变量名重复 de了半天bug愣是没找到错在哪 😅

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;

typedef long long LL;
typedef pair<int, int>PII;
inline LL gcd(LL a, LL b) {
          
    return b ? gcd(b, a % b) : a; }

const int N = 100010;

LL x, y;
char s[N];
int st[N][3], ed[N][3]; //记录前缀、后缀中 0、1、？的个数
vector<int>vec;

void solve() {
          
   
	scanf("%s", s + 1);
	cin >> x >> y;
	int len = strlen(s + 1);
	for (int i = 1; i <= len; ++i) {
          
    //前缀
		st[i][0] = st[i - 1][0];
		st[i][1] = st[i - 1][1];
		st[i][2] = st[i - 1][2];
		if (s[i] == 0)st[i][0]++;
		else if (s[i] == 1)st[i][1]++;
		else {
          
   
			vec.push_back(i);
			st[i][2]++;
		}
	}

	for (int i = len; i >= 1; --i) {
          
    //后缀
		ed[i][0] = ed[i + 1][0];
		ed[i][1] = ed[i + 1][1];
		ed[i][2] = ed[i + 1][2];
		if (s[i] == 0)ed[i][0]++;
		else if (s[i] == 1)ed[i][1]++;
		else ed[i][2]++;
	}

	LL sum0 = 0, sum1 = 0;
	LL ans = 0;

	for (int i = 1; i <= len; ++i) {
          
    //先求出把 ? 当作 1 时的的“愤怒值”
		if (s[i] == 0) {
          
   
			ans += sum1 * y;
			sum0++;
		}
		else {
          
   
			ans += sum0 * x; //把 ? 先看做是 1
			sum1++;
		}
	}

	LL res = ans;
	if (x < y) {
          
    //把 ? 当作 1 尽量放在前面 从后往前 将 ? 用 0 替换 遍历每种情况求最小值
		for (int i = 0; i < vec.size(); ++i) {
          
   
			int idx = vec[i];
			res = res - (st[idx - 1][0] + st[idx - 1][2]) * x - ed[idx + 1][0] * y;
			res = res + st[idx - 1][1] * y + (ed[idx + 1][1] + ed[idx + 1][2]) * x;
			ans = min(res, ans);
		}

	}
	else {
          
    //把 ? 当作 1 尽量放在后面 从前往后 将 ? 用 0 替换 遍历每种情况求最小值
		for (int i = vec.size() - 1; i >= 0; --i) {
          
   
			int idx = vec[i];
			res = res - st[idx - 1][0] * x - (ed[idx + 1][0] + ed[idx + 1][2]) * y;
			res = res + (st[idx - 1][1] + st[idx - 1][2]) * y + ed[idx + 1][1] * x;
			ans = min(res, ans);
		}
	}

	cout << ans << endl;





}
int main() {
          
   
	//int t; cin >> t;
	//while (t--)
	solve();

	return 0;
}