洛谷3558 [POI2013]BAJ-Bytecomputer

题意

有一个只有 $-1,0,1$ 的序列，每次操作可以使 s[i]+=s[i-1] ，求最少要操作几次使得序列单调不降。无解输出 BARK

序列长度 $N\le 1000000$ 。

题解

用 $f[i][j]$ 表示前 $i$ 个数，$s[i]=j-1$ 时的最少操作次数。然后对于每一位的值分类讨论即可。

代码里很显然了，我懒得再写一遍了。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int inf=0x3f3f3f3f;
int n,s[1000005],f[1000005][3];

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read();
    memset(f,0x3f,sizeof(f));
    f[1][s[1]+1]=0;
    for (int i=2;i<=n;i++)
    {
        if (s[i]==-1)
        {
            f[i][0]=f[i-1][0];
            f[i][2]=f[i-1][2]+2;
        }
        else if (s[i]==0)
        {
            f[i][0]=f[i-1][0]+1;
            f[i][1]=min(f[i-1][0],f[i-1][1]);
            f[i][2]=f[i-1][2]+1;
        }
        else if (s[i]==1)
        {
            f[i][0]=f[i-1][0]+2;
            f[i][1]=f[i-1][0]+1;
            f[i][2]=min(f[i-1][0],min(f[i-1][1],f[i-1][2]));
        }
    }
    int ans=min(f[n][0],min(f[n][1],f[n][2]));
    if (ans>=inf) return 0&puts("BRAK");
    printf("%d",ans);
    system("pause");
    return 0;
}