BZOJ 3427 「POI2013」Bytecomputer

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

很显然最后的序列是长成这样的：−1,…,−1,0,…,0,1,…,1。

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

fi,−1={fi−1,−1,ai=−1fi−1,−1+1,ai=0fi−1,−1+2,ai=1

fi,0={∞,ai=−1min(fi−1,−1,fi−1,0),ai=0fi−1,−1+1,ai=1

fi,1={fi−1,1+2,ai=−1fi−1,1+1,ai=0min(fi−1,−1,fi−1,0,fi−1,1),ai=1

如果无法理解转移方程，请时刻考虑单调性。

同时注意因为语言问题，我们可以把每个数 +1。

代码：

#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])));
}