【BZOJ1122】[POI2008] 账本BBB

正解：贪心加单调队列优化

先粘贴一张别人写的被老师发下来给我们的题解（就是看着这张题解才写出来的）

下面是自己的话（一些具体操作过程）：

把环拆成一条2*n的链，然后用优先队列来求出每一个区间的最小前缀和（先不考虑p)，存在了fM[]里面。

然后枚举起点（即第二次操作的使用次数）算出此时的费用cost去更新ans。

要注意的是，如果此时我需要将几个加号改成减号，按贪心的思路就是将最后几个加号改掉，这样的话，是不会影响这个区间的最小前缀和的（为什么呢？这个应该很好想吧），因为最小前缀和一定会以负号作为结尾，而Q是大于等于零的，如果这时改掉最后几个加号会使前缀和变负数的话，怎么可能最终加到Q呢？

代码~

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 
 7 #define For(i,a,b) for(register int i=a;i<=b;++i)
 8 #define Dwn(i,a,b) for(register int i=a;i>=b;--i)
 9 #define Re register
10 
11 using namespace std;
12 const int N=1e6+10;
13 int s[N*2],a[N*2];
14 struct Qr{
15     int x,st;
16 }q[N*4];
17 int n,m,x,y,Q,P,fM[N*2],cost,ans=2147483600;
18 inline void read(int &v){
19     v=0;
20     char c=getchar();
21     while(c<'0'||c>'9')c=getchar();
22     while(c>='0'&&c<='9')v=v*10+c-'0',c=getchar();
23 }
24 int main(){ 
25     read(n); read(P); read(Q); read(x); read(y);
26     For(i,1,n){
27         char c=getchar();
28         while(c!='-'&&c!='+')c=getchar();
29         if(c=='-')a[i]=a[i+n]=-1;
30         else a[i]=a[i+n]=1;
31     }
32     For(i,1,n*2)s[i]=s[i-1]+a[i];
33     
34     int f,r;
35     f=1; r=0;
36     Dwn(i,n*2-1,1){
37         int rx=i+n-1;
38         while(f<=r&&q[f].st>rx)f++;
39         while(f<=r&&q[r].x>=s[i])r--;
40         q[++r].x=s[i]; q[r].st=i;
41         if(i<=n)fM[i]=q[f].x-s[i-1]; 
42     }
43     int nd=(Q-P-s[n])/2;
44 
45     Dwn(i,n+1,2){ 
46         cost=y*(n+1-i)+abs(nd)*x; 
47         
48         int Ms;
49         if(i==n+1)Ms=fM[1];
50         else Ms=fM[i]; 
51         
52         if(nd>=0)Ms+=P+nd*2;
53         else Ms+=P;
54         
55         if(Ms<0)cost+=2*x*((1-Ms)/2);
56         ans=min(ans,cost);
57     }
58     cout<<ans<<endl;
59 }

【BZOJ1122】[POI2008] 账本BBB

相关推荐