题目概述

CF1464B

解题报告

我太菜了，这种题的思路其实挺经典的。

考虑相邻两个?之间的情况，假设他们之间有 $s_0$ 个 $0$ 和 $s_1$ 个 $1$ ：

• 第一个放 $0$ 第二个放 $1$ ，贡献是 $s_1x+s_0x+x+W=(s_0+s_1+1)x+W$
• 第一个放 $1$ 第二个放 $0$ ，贡献是 $s_0y+s_1y+y+W=(s_0+s_1+1)y+W$

其中 $W$ 是他们之间和外部产生的贡献，显然是相同的。

也就是说，如果 $x<y$ ，那么相邻两个?一定不会放 $10$ ，因为可以交换这两个?变成 $01$ ，答案更优，如果 $x\ge y$ 则同理。

那么如果 $x<y$ ，一定是前若干个?放了 $0$ ，后面的全放 $1$ 。如果 $x\ge y$ ，一定是前若干个?放了 $1$ ，后面的全放 $0$（不然交换之后更优）。这就可以通过预处理+枚举算出最优解了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,X,Y,pre[maxn+5][3],suf[maxn+5][3];char s[maxn+5];LL now,ans;

int main(){
    scanf("%s",s+1);n=strlen(s+1);
    for (int i=1;i<=n;i++) s[i]=='?'?s[i]=2:s[i]-='0';
    scanf("%d%d",&X,&Y);
    if (X>Y) {swap(X,Y);for (int i=1;i<=n;i++) if (s[i]<2) s[i]^=1;}
    for (int i=1;i<=n;i++){
        for (int j=0;j<3;j++) pre[i][j]=pre[i-1][j];
        pre[i][s[i]]++;
    }
    for (int i=n;i;i--){
        for (int j=0;j<3;j++) suf[i][j]=suf[i+1][j];
        suf[i][s[i]]++;
    }
    for (int i=1;i<=n;i++)
        if (s[i]==0) now+=(LL)(pre[i-1][1]+pre[i-1][2])*Y;
        else now+=(LL)pre[i-1][0]*X;
    ans=now;
    for (int i=1;i<=n;i++)
        if (s[i]==2){
            now-=(LL)(pre[i-1][0]+pre[i-1][2])*X+(LL)suf[i+1][0]*Y;
            now+=(LL)pre[i-1][1]*Y+(LL)(suf[i+1][1]+suf[i+1][2])*X;
            if (now<ans) ans=now;
        }
    printf("%lld\n",ans);return 0;
}