1122: [POI2008]账本BBB
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 467 Solved: 232[][][]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
Sample Output
HINT
Source
神题啊！！可惜依然懵的一比……
http://www.cnblogs.com/Pumbit-Legion/p/5962627.html
记录一下序列前缀和
若p+序列和≠q，可以发现取反操作数量是确定的
且尽量在前面做加法，后面做减法
至于旋转操作，暴力想法是把最后一位提前，就相当于连成一个环，在环上求值
所以在环上枚举起点，就相当于移动操作
要是移动不能满足非负，还可以把前面的-操作改为+，对应的后面的+改为-
但暴力走一遍环单纯是为了解决非负的问题
而对于一个起点的序列，若已知其最小值并把它修改至大于0，则显然前后值都不会小于零(想象前缀和)
所以在环上用单调队列求一遍最小值，再枚举起点做无旋转的修改，求最小花费
而题目保证有解题目保证有解题目保证有解
所以除了必要的修改，还需要前后取反时，使最终序列和满足要求的操作一定已经用完了(不论是+变-还是-变+)
那么直接在最小值上加上取反得到的值(一定要大于0)，如果还小的话再前后取反
(要是必要的操作是减变加，因为题目有解，所以修改操作一定不在最小值位置之前)
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=1e6+6; 5 LL n,p,q,x,y; 6 LL que[MAX*2],sum[MAX*2],mn[MAX];//mn[i]表示以i为起点,后面n个数中按照操作会出现的最小的数 7 char s[MAX]; 8 int main(){ 9 freopen ("bbb.in","r",stdin);10 freopen ("bbb.out","w",stdout);11 LL i,j,low,high;12 scanf("%lld%lld%lld%lld%lld\n",&n,&p,&q,&x,&y);13 gets(s+1);14 memset(sum,0,sizeof(sum));15 for (i=n<<1;i>n;i--) sum[i]=sum[i+1]+(s[i-n]=='+'?1:-1);16 for (;i;i--) sum[i]=sum[i+1]+(s[i]=='+'?1:-1);17 memset(que,0,sizeof(que));18 low=1;high=0;19 for (i=n<<1;i;i--){20 while (low<=high && sum[i]>sum[que[high]]) high--; que[++high]=i;21 while (low<=high && que[low]-i>=n) low++;22 if (i<=n) mn[i]=sum[i]-sum[que[low]];23 }24 LL ss=sum[n+1],tmp=(q-p-ss)/2,ans=1e18,zt;25 for (i=0;i