最近打算开始练练 DP，提升一下思维。
这题其实比较显然吧，只要读透了题（虽然没多少）就很好想到了。
很显然最后的序列是长成这样的：\(-1,\dots,-1,0,\dots,0,1,\dots,1\)。
设 \(f_{i,j}\) 表示使得前 \(i\) 个数满足单调不降，第 \(i\) 个数为 \(j\) 的最小方案。
那么显然有
\[ f_{i,-1} = \begin{cases} f_{i-1,-1},& a_i = -1\\ f_{i-1,-1} + 1,& a_i = 0\\ f_{i-1,-1} + 2,& a_i = 1 \end{cases} \]
\[ f_{i,0} = \begin{cases} \infty,& a_i = -1\\ \min(f_{i-1,-1},f_{i-1,0}),& a_i = 0\\ f_{i-1,-1} + 1,& a_i = 1 \end{cases} \]
\[ f_{i,1} = \begin{cases} f_{i-1,1} + 2,& a_i = -1\\ f_{i-1,1} + 1,& a_i = 0\\ \min(f_{i-1,-1},f_{i-1,0},f_{i-1,1}),& a_i = 1 \end{cases} \]
如果无法理解转移方程，请时刻考虑单调性。
同时注意因为语言问题，我们可以把每个数 \(+1\)。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using namespace std;
const int N = 1e6;
int n,a[N + 5],f[N + 5][3];
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),++a[i];
memset(f,0x3f,sizeof f);
f[1][a[1]] = 0;
for(register 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;
else if(a[i] == 1)
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
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]));
if(min(f[n][0],min(f[n][1],f[n][2])) == 0x3f3f3f3f)
puts("BRAK");
else
printf("%d\n",min(f[n][0],min(f[n][1],f[n][2])));
}