bzoj1122:[POI2008]账本BBB

传送门

异常激动，跑了bzoj的rank2
这个题一共有两个要求，先考虑第二个要求，可以知道每一次修改都会导致答案账户余额+2/-2
所以修改方案是唯一的，可以\(O(1)\)算出来
然后考虑第一个要求，显然有结论：如果当前值为负，你可以修改当前位置之前的一个负号为正号，并且修改当前位置之后的一个正号为负号来使最小值+2
然而你也可以移动最后的符号使最小值不小于0
于是我们就得出了一个算法：先算出需要修改多少个符号来满足第二个要求，如果是将负号修改为正号，便可以将最小值升高，如果最小值依然小于0，那么枚举移动最后的数的个数，同时使用那个结论，得出最小的修改代价，统计到答案中
代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
    char ch; bool ok;
    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1e6+10;
int n,p,q,x,y,mp[maxn],sum[maxn],nsum[maxn],mx,now,mn,ans;char ch[maxn];
int main()
{
    read(n),read(p),read(q),read(x),read(y),scanf("%s",ch+1);
    for(rg int i=1;i<=n;i++)mp[i]=ch[i]=='-'?-1:1,mx+=mp[i];
    mx=(q-mx-p)/2,now=p,ans=abs(mx)*x;
    for(rg int i=1;i<=n;i++)now+=mp[i],mn=min(mn,now);
    if(mn<0)
    {
        if(mx>0)mn+=mx*2;now=0;int a=0,b=1e9;
        if(mn<0)
        {
            if(mn&1)b=(abs(mn)/2+1)*2*x;
            else b=abs(mn)/2*2*x;
            for(rg int i=n;i>=1;i--)
            {
                now+=mp[i];if(now+mn>=0){b=min(y*(n-i+1),b);break;}
                a=y*(n-i+1);
                if(mn+now<0)
                {
                    int g=mn+now;
                    if(g&1)a+=(abs(g)/2+1)*2*x;
                    else a+=abs(g)/2*2*x;
                }
                b=min(b,a);
            }
            ans+=b;
        }
    }
    printf("%d\n",ans);
}

bzoj1122:[POI2008]账本BBB

原文：https://www.cnblogs.com/lcxer/p/10388491.html