标签：color size 结果 16px har can end 获得 减法
https://codeforces.ml/contest/1465/problem/D
参考：https://www.cnblogs.com/JDFZ-ZZ/p/14171488.html & https://blog.csdn.net/weixin_43918473/article/details/111879784
分别从前往后预处理前面的1的数量，从后往前预处理后面0的数量。
通过减法可以获得相应0和1的数量，对于‘？’正序预处理将其视为0，逆序预处理将其视为1。
对于某一个位置，我们先求出外部结果，也即pre[i] + suf[i + 1]
然后是二者组间数量，有两部分，也即prec[i] * sufc[i + 1] * y和(i - prec[i]) * (len - i - sufc[i + 1]) * x的和
扫一遍求最小值。
看了半天才看懂...我好笨555
1 #include<bits/stdc++.h>
2 #define ll long long
3 using namespace std; 4 const int N = 1e5 + 10; 5 char s[N]; 6 ll x, y; 7 ll prec[N], sufc[N], pre[N], suf[N]; 8 //前1的个数，后0的个数
9 int main(){ 10 scanf("%s", s + 1); 11 scanf("%lld %lld",&x, &y); 12 int len = strlen(s + 1); 13
14 if(x > y){ 15 swap(x, y); 16 for(int i = 1 ; i <= len ; i++){ 17 if(s[i] == ‘0‘) s[i] = ‘1‘; 18 else if(s[i] == ‘1‘) s[i] = ‘0‘; 19 } 20 //reverse(s.begin(), s.end());
21 } 22
23 ll res = (1ll << 61); 24 for(int i = 1 ; i <= len ; i++){ 25 if(s[i] == ‘1‘){ 26 prec[i] = prec[i - 1] + 1; 27 pre[i] = pre[i - 1] + 1ll * (i - prec[i]) * x; 28 }else{ 29 prec[i] = prec[i - 1]; 30 pre[i] = pre[i - 1] + prec[i] * y; 31 } 32 } 33
34 for(int i = len ; i >= 1 ; i--){ 35 if(s[i] == ‘0‘){ 36 sufc[i] = sufc[i + 1] + 1; 37 suf[i] = suf[i + 1] + (len - i + 1 - sufc[i]) * x; 38 }else{ 39 sufc[i] = sufc[i + 1]; 40 suf[i] = suf[i + 1] + (sufc[i] * y); 41 } 42 } 43 for(int i = 0 ; i <= len ; i++){ 44 res = min(res, pre[i] + suf[i + 1] + prec[i] * sufc[i + 1] * y + (ll)(i - prec[i]) * (len - i - sufc[i + 1]) * x); 45 // 前预处理+后预处理组内数量 + 前面1的数量*后面0的数量*y + 前0数*后1数*x
46 } 47 printf("%lld\n", res); 48
49 return 0; 50 }
CF 1465D Grime Zoo
标签：color size 结果 16px har can end 获得 减法
原文地址：https://www.cnblogs.com/ecustlegendn324/p/14292797.html
暂无评论...
