原题链接
考察:贪心
本蒟蒻想的是线性dp,时间复杂度太高否了(.),然后又想不到正解.
思路:
参考了大佬的题解,就结果而言,最后要么是?序列0,1两极分布,要么是0,1混合分布.
对于混合分布,对于每一个相邻的?,要么是0,1要么是1,0.假设两个相邻?之间有s0个0,s1个1.
如果首尾填01那么这段对评论数的贡献是:s0x+s1x+x+外部对内部的贡献W
如果首尾填10那么这段对评论数的贡献是:s0y+s1y+y+外部对内部的贡献W
显然,如果x>y,我们需要将每一对相邻的?的01换成10,同理x<y.假定x>y,每个01都会被换成10,最后无法交换一定是不存在01,那么此时?构成的01序列一定是10两极分布,但是此时不能确定全填0或1就是最优的,所以需要枚举分界点.最后求出答案即可.
比较好的计算思路是先将?全填1或0,对于每个替换进行+-操作.
Code
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 100010;
char s[N];//dp的时间复杂度太高
int n,x,y,st[N][3],ed[N][3];
vector<int> v;
void init()
{
for(int i=1;i<=n;i++)
{
if(s[i]=='?')
{
st[i][2]++;
v.push_back(i);
}else st[i][s[i]-'0']++;
for(int j=0;j<3;j++) st[i][j]+=st[i-1][j];
}
for(int i=n;i>=1;i--)
{
if(s[i]=='?') ed[i][2]++;
else ed[i][s[i]-'0']++;
for(int j=0;j<3;j++) ed[i][j]+=ed[i+1][j];
}
}
void solve()
{
LL ans = 0,res;
for(int i=1;i<=n;i++)
{
if(s[i]=='0') ans+=(LL)(st[i-1][1]+st[i-1][2])*y;
else ans+=(LL)st[i-1][0]*x;
}
res = ans;
if(x<=y)//填01更好
{
for(int i=0;i<v.size();i++)
{//枚举前i个填0
int j = v[i];
res-=(LL)(st[j-1][0]+st[j-1][2])*x+(LL)ed[j+1][0]*y;
res+=(LL)st[j-1][1]*y+(LL)(ed[j+1][1]+ed[j+1][2])*x;
ans = min(res,ans);
}
}else{//填10 改成0
for(int i=v.size()-1;i>=0;i--)
{
int j = v[i];
res-=(LL)st[j-1][0]*x+(LL)(ed[j+1][0]+ed[j+1][2])*y;
res+=(LL)(st[j-1][1]+st[j-1][2])*y+(LL)ed[j+1][1]*x;
ans = min(res,ans);
}
}
printf("%lld\n",ans);
}
int main()
{
scanf("%s%d%d",s+1,&x,&y);
n = strlen(s+1);
init();
solve();
return 0;
}