（前綴后綴+思維+貪心）
D. Grime Zoo
題目傳送門：
D. Grime Zoo
題目大意：
給你一個由‘0’ 和‘1’和 ‘?‘組成，其中有一個01子序列就會產生x點憤怒值，每有一個10子序列就會產生y點憤怒值，其中問號’?'可以變成0或者是1，問憤怒值的和最小為多少，
思路：
我借鑒了許多人的想法之后，我個人比較好理解的想法是：
當一個序列中0和1的數量固定時，子序列00和11的數量也是固定的，子序列01+10的數量也是固定的，那么當x>y時，我們貪心的想要01盡可能少，10盡可能的多，于是我們把1盡量往前填，而當x<y時，我們想01盡可能多，10盡可能少，于是我們把1盡量往后填，具體實作的細節看代碼，
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
char str[N];
LL x,y;
int st[N][3],ed[N][3];//記錄每個位置之前0,1,'?'的數量
vector<int>g;//存下每個問號的位置
int main()
{
scanf("%s",str+1);
scanf("%lld%lld",&x,&y);
int len=strlen(str+1);
for(int i=1;i<=len;i++)
{//求前綴
st[i][0]=st[i-1][0];
st[i][1]=st[i-1][1];
st[i][2]=st[i-1][2];
if(str[i]=='0') st[i][0]++;
else if(str[i]=='1') st[i][1]++;
else
{
st[i][2]++;
g.push_back(i);
}
}
for(int i=len;i>=1;i--)
{//求后綴
ed[i][0]=ed[i+1][0];
ed[i][1]=ed[i+1][1];
ed[i][2]=ed[i+1][2];
if(str[i]=='0') ed[i][0]++;
else if(str[i]=='1') ed[i][1]++;
else ed[i][2]++;
}
LL num0=0,num1=0;//記錄前綴中0和1的數量(先把'?'都先看成是1)
LL ans=0;
for(int i=1;i<=len;i++)
{
if(str[i]=='0')
{
ans=ans+num1*y;
num0++;
}
else
{
ans=ans+num0*x;
num1++;
}
}
LL res=ans;
if(x<y)//10的憤怒值貢獻高，所以我們盡量把1放在后面
{
for(int i=0;i<g.size();i++)//從前往后遍歷每個問號的位置，并把它變成0
{
int idx=g[i];
res=res-(st[idx-1][0]+st[idx-1][2])*x-ed[idx+1][0]*y;
res=res+st[idx-1][1]*y+(ed[idx+1][1]+ed[idx+1][2])*x;
ans=min(res,ans);
}
}
else
{//01的憤怒值高，所以我們盡量把1放前面
for(int i=g.size()-1;i>=0;i--)
{//從后往前遍歷問號的位置，并把它變成0
int idx=g[i];
res=res-st[idx-1][0]*x-(ed[idx+1][0]+ed[idx+1][2])*y;
res=res+(st[idx-1][1]+st[idx-1][2])*y+ed[idx+1][1]*x;
ans=min(res,ans);
}
}
printf("%lld\n",ans);
//system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/238592.html
標籤：其他
上一篇：PTA 8習題講解