给你一串01字符串你可以花费a引爆一串连续的1或者花费b让一个0变成1。问引爆这串字符串的所有1需要多少花费。假设这串字符的1的联通块个数有num个则他们之间0的联通块为num-1个。若ab则ans为num*a因为填补中间零加上引爆一次的花费至少为num-1ba直接引爆的花费为numa因为ab故后者小。若ab我们则处理出每两个1直接的0的个数从小往大遍历设当前0的个数为x若xba2a则填补这些0。故我们计算a的贡献次数和b的贡献次数a原本贡献次数为num每次填补都会贡献x次b使a减少一次贡献因为连着一起引爆了。#includeiostream#includestring.h#includealgorithmusingnamespacestd;constintmaxn1e55;typedeflonglongll;intt,a,b,num1,len,flag;chars[maxn];intnum[maxn];ll ans;intmain(){cint;while(t--){cinab;cins1;num10;lenstrlen(s1);flag1;ans0;for(inti1;ilen;i){if(s[i]1flag){num1;flag0;}if(s[i]0){flag1;}}if(ab){coutnum1*a\n;continue;}intk0,now0;flag0;for(inti1;ilen;i){if(s[i]0flag){now;}if(s[i]1now){num[k]now;now0;}if(s[i]1)flag1;}sort(num1,num1k);intcnt0;for(inti1;ik;i){if(num[i]*ba2*a){ansnum[i];cnt;}elsebreak;}ansans*b(num1-cnt)*a;coutans\n;}}/* 100 1 1 00110001100101 */
配置详解：预算控制、承诺预算与可用性检查)
