BZOJ1122: [POI2008]账本BBB 单调性+贪心

题解：

对于自己目前的状态实在是不想多说。。。

考虑如果没有操作2的话怎么做。

首先算出最小前缀和，如果<0的话贪心将前面的若干个-1改成+1。这个可以$O(1)$计算。

现在一定能保证任意前缀均$\geq{0}$。

但是最终不一定是$q$。

我们算出如果想要让最终结果为$q$需要将多少-1变为1或者将1变成-1。

将-1变成1显然不会违反前缀$\geq{0}$的条件。

考虑将1变成-1，我们贪心的将最后的1变成-1，由于原来的总量是$>q$的（所以才要将1变成-1），容易证明这样修改依然满足条件。

那么只需要处理循环序列的最小前缀和，利用单调队列$O(n)$处理即可。

代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 1000010
char s[N<<1];

int f[N<<1];
int q[N<<1],fr,ta;
int abs(int x){
	return x<0?-x:x;
}
int main(){
	int n,p,q,x,y,i,j;
	scanf("%d%d%d%d%d",&n,&p,&q,&x,&y);
	scanf("%s",s+1);
	for(i=n+1;i<2*n;++i)
		s[i]=s[i-n];
	int ans=0x3f3f3f3f,mn,temp,cost;
	for(i=1;i<2*n;++i){
		while(fr!=ta&&::q[fr]<=i-n)
			++fr;
		f[i]=f[i-1]+((s[i]=='-')?-1:1);
		while(fr!=ta&&f[i]<=f[::q[ta-1]])
			--ta;
		::q[ta++]=i;
		if(i>=n){
			mn=p+f[::q[fr]]-f[i-n];
			cost=0;
			temp=p+f[n];
			if(mn<0){
				cost=(1-mn)/2*x;
				temp+=(1-mn)/2*2;
			}
			ans=min(ans,cost+x*(abs(temp-q)/2)+y*((n*2-i)%n));
		}
	}
	cout<<ans<<endl;
	return 0;
}