模拟赛被这题创飞了，所以来写篇题解纪念一下。

• 首先我们先考虑暴力：

  • 注意到取反和位移的顺序是不影响答案的。
  • 所以我们可以 $\Theta(2^n)$ 枚举对哪一个位置取反。
  • 再 $\Theta(n)$ 枚举位移几次。
  • 最后再 $\Theta(n)$ 判断是否合法并更新答案。
  • 最后实现复杂度为 $O(2^n n^2)$。

• 我们考虑贪心：

  • $\Theta(n)$ 的枚举位移次数。
  • 记原来的账本 $a_1,a_2,...,a_n$，其中 + 对应 $a_i=1$，- 对应 $a_i=-1$。
  • 那么进行了 $k$ 次位移操作之后得到的 $a$ 数组就是 $a_{1+k \bmod n},a_{2+k \bmod n},...,a_{n+k \bmod n}$。
  • 我们再求出 $a$ 数组的前缀和：$$s_i=\sum^{i}_{j=0} a_{j+k \bmod n}$$
  • 为了保证每一个 $s_i$ 都是非负的，所以我们计算的时候如果 $s_i<0$ 那么就在前面进行若干次取反操作使得 $s_i = 0$ 再记下来并记录对于 $s_n$ 的影响。
  • 再记 $o$ 为 $q-(p+s_n)$ 的绝对值，我们再调整 $\frac{o}{2}$ 次就行（至于为啥要除二建议读者自己去想一下）。
  • 时间复杂度：$\Theta(n^2)$。

• 最后是正解：

  • 注意到操作的代价是可以 $\Theta(1)$ 计算。
  • 为了方便可以将 $a$ 再复制一遍，变成一个长度为 $2n$ 的链。
  • 对扩展后的 $a$ 数组求一个前缀和 $t$，则进行 $k$ 次位移的最小值为 $t$ 在区间 $[k,k+n-1]$ 上最小值的位置。

Ac Code：

#include<bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define int long long
#define R register
#define rint register int
#define _ read<int>()
inline bool blank(const char x)
{
    return !(x^9)||!(x^13)||!(x^10)||!(x^32);
}
template<class T>inline T read()
{
    T r=0,f=1;R char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(int x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}
inline void read(char &x)
{
    for(x=gc();blank(x)&&(x^-1);x=gc());
}
const int N=2e6+10;
string s;
int n,p,q,x,y,sum[N],a[N];
deque<int> dq;

signed main()
{
    n=_,p=_,q=_,x=_,y=_;
    cin>>s;
    s=' '+s;
    for(rint i=1;i<=n;i++)
    {
        if(s[i]=='-') a[i]=-1;
        else a[i]=1;
        sum[i]=sum[i-1]+a[i];
    }
    for(rint i=n+1;i<=(n<<1);i++)
    {
        sum[i]=sum[i-1]+a[i-n];
    }
    rint tmp=p+sum[n];
    rint d=abs(q-tmp)/2*x;
    rint ans=1145141919810;
    for(rint i=0;i<=n;i++)
    {
        while(!dq.empty()&&sum[dq.back()]>=sum[i])
            dq.pop_back();
        dq.push_back(i);
    }
    for(rint i=n+1;i<=(n<<1);i++)
    {
        while(!dq.empty()&&sum[dq.back()]>=sum[i]) dq.pop_back();
        dq.push_back(i);
        while(!dq.empty()&&dq.front()<i-n) dq.pop_front();
        if(i>=n)
        {
            rint k=2*n-i;
            rint minv=sum[dq.front()]-sum[i-n]+p+max(q-tmp,0LL);
            rint nd=max(1-minv,0LL)/2*x*2;
            ans=min(ans,k*y+nd);
        }
    }
    out(ans+d);
    return 0;
}