注意到题目给的条件,序列初始只有 $-1,0,1$,猜一下最终的数列在最优情况下也都是 $-1,0,1$
证明也挺显然吧,如果一个数初始为 $-1$ ,并且前面一个数是正数,那么这个正数为了让 $-1$ 变成大于等于它的数,不论如何都必须操作两次
如果一个数初始为 $0$ ,那么要变成大于等于前面的数也一定只要一次操作,对于 $1$ 的情况也是同理
所以推广一下最优情况每个位置都是 $-1,0,1$
然后直接 $dp$ 即可,复杂度 $O(n)$
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e6+7; int n,a[N]; int f[N][3]; int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read()+1; memset(f,0x3f,sizeof(f)); f[1][a[1]]=0; for(int i=2;i<=n;i++) { if(a[i]==0) { f[i][0]=f[i-1][0]; f[i][2]=f[i-1][2]+2; } if(a[i]==1) { f[i][0]=f[i-1][0]+1; f[i][1]=min(f[i-1][1],f[i-1][0]); f[i][2]=f[i-1][2]+1; } if(a[i]==2) { f[i][0]=f[i-1][0]+2; f[i][1]=f[i-1][0]+1; f[i][2]=min(f[i-1][2],min(f[i-1][0],f[i-1][1])); } } int ans=min(f[n][0],min(f[n][1],f[n][2])); if(ans>=f[0][0]) printf("BRAK\n"); else printf("%d\n",ans); return 0; }