首页 > 代码库 > [bzoj1122][POI2008]账本BBB

[bzoj1122][POI2008]账本BBB

1122: [POI2008]账本BBB

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 402  Solved: 202
[Submit][Status][Discuss]

Description

一个长度为n的记账单,+表示存¥1,-表示取¥1。现在发现记账单有问题。一开始本来已经存了¥p,并且知道最后账户上还有¥q。你要把记账单修改正确,使得 1:账户永远不会出现负数; 2:最后账户上还有¥q。你有2种操作: 1:对某一位取反,耗时x; 2:把最后一位移到第一位,耗时y。

Input

The first line contains 5 integers n, p, q, x and y (1  n  1000000, 0  p;q  1000000, 1  x;y  1000), separated by single spaces and denoting respectively: the number of transactions done by Byteasar, initial and final account balance and the number of seconds needed to perform a single turn (change of sign) and move of transaction to the beginning. The second line contains a sequence of n signs (each a plus or a minus), with no spaces in-between. 1 ≤ n ≤ 1000000, 0 ≤ p ,q ≤ 1000000, 1 ≤x,y ≤ 1000)

Output

修改消耗的时间

Sample Input

9 2 3 2 1
---++++++

Sample Output

3

HINT

 

Source

 

老师的惊天模拟赛#2

TAT还是不会

相当神的题目

记录一下序列前缀和

若p+序列和≠q,可以发现取反操作数量是确定的

且尽量在前面做加法,后面做减法

至于旋转操作,暴力想法是把最后一位提前,就相当于连成一个环,在环上求值

所以在环上枚举起点,就相当于移动操作

要是移动不能满足非负,还可以把前面的-操作改为+,对应的后面的+改为-

但暴力走一遍环单纯是为了解决非负的问题

而对于一个起点的序列,若已知其最小值并把它修改至大于0,则显然前后值都不会小于零(想象前缀和)

所以在环上用单调队列求一遍最小值,再枚举起点做无旋转的修改,求最小花费

而题目保证有解题目保证有解题目保证有解

所以除了必要的修改,还需要前后取反时,使最终序列和满足要求的操作一定已经用完了(不论是+变-还是-变+)

那么直接在最小值上加上取反得到的值(一定要大于0),如果还小的话再前后取反

(要是必要的操作是减变加,因为题目有解,所以修改操作一定不在最小值位置之前)

还有好多细节,看代码

技术分享
 1   2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #define LL long long 7 int que[2000020],seq[2000020],mn[1000010]; 8 char opt[1000002]; 9 inline LL abs(LL a){10     return a>0?a:-a;11 }12 inline LL max(LL a,LL b){13     return a>b?a:b;14 }15 inline LL min(LL a,LL b){16     return a<b?a:b;17 }18 int main(){19     LL n,p,q,x,y;20     int i,h,t;21     scanf("%lld %lld %lld %lld %lld",&n,&p,&q,&x,&y);22     scanf("%s",opt+1);23     for(i=n<<1;i>n;--i)seq[i]=seq[i+1]+(opt[i-n]==+?1:-1);24     for(i=n;i;--i)seq[i]=seq[i+1]+(opt[i]==+?1:-1);25     que[0]=0;26     h=1,t=0;27     for(i=n<<1;i;--i){28         while(h<=t&&seq[i]>seq[que[t]])--t;//seq[i]-seq[que[h]]>seq[que[t]]-seq[que[h]]29         que[++t]=i;30         while(h<=t&&que[h]-i>=n)++h;31         if(i<=n)mn[i]=seq[i]-seq[que[h]]; //你不能用head更新min,只能倒序用i 32     }33     LL all=seq[n+1],tmp=(q-p-all)/2,ans=1e16,cst;34     for(i=0;i<n;i++){//枚举起点与枚举旋转次数不同 35         cst=x*abs(tmp)+y*(LL)i;36         if(i==0){37             mn[1]+=p+max(tmp,0)*2;38             if(mn[1]<0)cst+=2*x*((1-mn[1])/2);39         }else{40             mn[n-i+1]+=p+max(tmp,0)*2;41             if(mn[n-i+1]<0)cst+=2*x*((1-mn[n-i+1])/2);42         }43         ans=min(ans,cst);44     }45     printf("%lld",ans);46     return 0;47 }
View Code

 

[bzoj1122][POI2008]账本BBB