Description：

给一个只包含 $-1,0,1$ 的数列，每次操作可以让 $a[i]+=a[i-1]$ ，求最少操作次数使得序列单调不降。

$1\le n \le 1000000$

Solution：

设 $f[i][0/1/2]$ 表示第 $i$ 位最后被加成了 $-1/0/1$ 的最少操作次数，转移时分类讨论一下，注意 $a[i]+=a[i-1]$ 的 $a[i-1]$ 是被加完之后的，初值为 $f[1][a[1]]=0$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int a[MAXN];

int f[MAXN][3];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	memset(f,0x3f,sizeof(f));

	f[1][a[1] + 1] = 0;

	for(int i = 2;i <= n;++i)

	{

		if(a[i] == -1)

		{

			f[i][0] = f[i - 1][0];

			f[i][2] = f[i - 1][2] + 2;

		}

		if(a[i] == 0)

		{

			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] == 1)

		{

			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][1],f[i - 1][0]));

		}

	}

	int ans = min(f[n][2],min(f[n][1],f[n][0]));

	if(ans == 0x3f3f3f3f)puts("BRAK");

	else cout << ans << endl;

	return 0;

}