BZOJ 3427.「POI2013」Bytecomputer

最近打算开始练练 DP,提升一下思维。
这题其实比较显然吧,只要读透了题(虽然没多少)就很好想到了。

很显然最后的序列是长成这样的:

fi,jf_{i,j} 表示使得前 ii 个数满足单调不降,第 ii 个数为 jj 的最小方案。
那么显然有

fi,1={fi1,1,ai=1fi1,1+1,ai=0fi1,1+2,ai=1 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} fi,0={,ai=1min(fi1,1,fi1,0),ai=0fi1,1+1,ai=1 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} fi,1={fi1,1+2,ai=1fi1,1+1,ai=0min(fi1,1,fi1,0,fi1,1),ai=1 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

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
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])));
}