CF 1465D Grime Zoo

技术文章 8个月前 完美者
1,279 0

标签: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

版权声明:完美者 发表于 2021-01-19 12:01:51。
转载请注明:CF 1465D Grime Zoo | 完美导航

暂无评论

暂无评论...