首页 > 代码库 > BZOJ 1122 POI2008 账本BBB 单调队列
BZOJ 1122 POI2008 账本BBB 单调队列
题目大意:给定一个由
1.将某一位取反,花销为
2.将最后一位移动到前一位。花销为
要求终于
枚举终于的序列以哪个点開始。那么从这个点往后的最小前缀和能够用单调队列预处理出来
然后贪心地把左边的
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 2002002
using namespace std;
int n,p,q;
long long x,y,ans=0x7fffffffffffffffll;
char s[M];
int sum[M],_min[M];
void Assert(bool flag)
{
if(flag)
return ;
printf("%d\n",1/0);
exit(0);
}
int main()
{
int i;
cin>>n>>p>>q>>x>>y;
scanf("%s",s+1);
for(i=n<<1;i>n;i--)
sum[i]=sum[i+1]+(s[i-n]==‘-‘?-1:1);
for(i=n;i;i--)
sum[i]=sum[i+1]+(s[i]==‘-‘?-1:1);
static int q[M],r,h;
for(i=n<<1;i;i--)
{
while( r-h>=1 && sum[q[r]]<sum[i] )
q[r--]=0;
q[++r]=i;
while( q[h+1]-i>n )
q[++h]=0;
if(i<=n)
_min[i]=sum[i]-sum[q[h+1]];
}
Assert( ~ (::q)-p - sum[n+1] & 1 );
int temp=(::q-p)-sum[n+1]>>1;
for(i=1;i<=n;i++)
{
long long cost=(n-i+1)%n*y+abs(temp)*x;
_min[i]+=p+max(temp,0)*2;
if(_min[i]<0)
cost+=(1-_min[i]>>1)*x*2;
if(cost<ans)
ans=cost;
}
cout<<ans<<endl;
return 0;
}
BZOJ 1122 POI2008 账本BBB 单调队列