【BZOJ1122】[POI2008] 账本BBB

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

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

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

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

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

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

代码~

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #define For(i,a,b) for(register int i=a;i<=b;++i)

 #define Dwn(i,a,b) for(register int i=a;i>=b;--i)

 #define Re register

 using namespace std;

 const int N=1e6+;

 int s[N*],a[N*];

 struct Qr{

     int x,st;

 }q[N*];

 int n,m,x,y,Q,P,fM[N*],cost,ans=;

 inline void read(int &v){

     v=;

     char c=getchar();

     while(c<''||c>'')c=getchar();

     while(c>=''&&c<='')v=v*+c-'',c=getchar();

 }

 int main(){

     read(n); read(P); read(Q); read(x); read(y);

     For(i,,n){

         char c=getchar();

         while(c!='-'&&c!='+')c=getchar();

         if(c=='-')a[i]=a[i+n]=-;

         else a[i]=a[i+n]=;

     }

     For(i,,n*)s[i]=s[i-]+a[i];

     int f,r;

     f=; r=;

     Dwn(i,n*-,){

         int rx=i+n-;

         while(f<=r&&q[f].st>rx)f++;

         while(f<=r&&q[r].x>=s[i])r--;

         q[++r].x=s[i]; q[r].st=i;

         if(i<=n)fM[i]=q[f].x-s[i-];

     }

     int nd=(Q-P-s[n])/;

     Dwn(i,n+,){

         cost=y*(n+-i)+abs(nd)*x; 

         int Ms;

         if(i==n+)Ms=fM[];

         else Ms=fM[i]; 

         if(nd>=)Ms+=P+nd*;

         else Ms+=P;

         if(Ms<)cost+=*x*((-Ms)/);

         ans=min(ans,cost);

     }

     cout<<ans<<endl;

 }

巴特西

【BZOJ1122】[POI2008] 账本BBB

最新文章

热门文章