题解--P3558 [POI2013]BAJ-Bytecomputer
前言：这是一道非常好的线性DP题，建议大家多理解该题的状态转移方程的推导过程，以便游刃有余的切其他DP题
好了，废话不多说，开始我们的解题之旅吧！
1.题意简述
给一个只包含
2.解题思路
1.首先，我们可以得到一个非常有用的结论--操作完成后的最终序列一定是一个只包含-1,0,1 的数列。
为了让大家都能理解透此题，我还是在下面先给出一段证明。（懂了的大佬可自行跳过）
1.如果操作完的序列包含
2.如果操作完的序列包含这不是多此一举、自找苦吃吗？
综上所述，操作完成后的最终序列一定是一个只包含
2.我们其实由第一个结论就可以推出无解的情况
1.如果该序列的第一个数是
2.如果该序列的第一个数是
3.如果该序列的第一个数是
若
若
好了，既然我们已经把握两大结论在手中，就可以直接莽结论（不要怂，就是干）。
状态表示及阶段划分
根据解DP题的
首先，题目要我们求最少操作次数，那我们就跟着题面走，令DP数组的值为最少操作次数。
其次，我们再思考一下DP数组要有几个维度，每一个维度分别求什么？我们观察一下我们推出的结论
自然，阶段划分也很明了，直接令到达
状态转移方程
做多了DP题的OIer都知道，DP方程是DP题最大的难点 （得之则生，弗得则死），就让我们一举攻破这一难关吧！
我们设当前下标为
当a[i]=-1 时
1.如果前一下标（
if(hav[i-1][1]) f[i][1]=f[i-1][1],hav[i][1]=1;又因为前一下标（
2.如果前一下标（
3.如果前一下标（
if(hav[i-1][3]) f[i][3]=f[i-1][3]+2,hav[i][3]=1;当a[i]=0 时
1.如果前一下标（
if(hav[i-1][1]) f[i][1]=f[i-1][1]+1,hav[i][1]=1,f[i][2]=f[i-1][1],hav[i][2]=1;2.如果前一下标（
if(hav[i-1][2]) f[i][2]=min(f[i][2],f[i-1][2]),hav[i][2]=1;3.如果前一下标（
if(hav[i-1][3]) f[i][3]=f[i-1][3]+1,hav[i][3]=1;当a[i]=1 时
1.如果前一下标（
if(hav[i-1][1]) f[i][1]=f[i-1][1]+2,hav[i][1]=1,f[i][2]=f[i-1][1]+1,hav[i][2]=1,f[i][3]=f[i-1][1],hav[i][3]=1;2.如果前一下标（
if(hav[i-1][2]) f[i][3]=min(f[i][3],f[i-1][2]),hav[i][3]=1;3.如果前一下标（
if(hav[i-1][3]) f[i][3]=min(f[i][3],f[i-1][3]),hav[i][3]=1;最后，我们确定一下DP的边界条件及DP目标
显然，DP的边界条件是
memset(f,INF,sizeof(f));
f[1][a[1]+2]=0;hav[1][a[1]+2]=1;而DP目标是
if(!hav[n][1]&&!hav[n][2]&&!hav[n][3]) printf("BRAK");
//都到不了下标为n的状态，就是无解
else printf("%d",min(f[n][1],min(f[n][2],f[n][3])));3.打了这么久，终于上代码了
1.用
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#define il inline
#define ll long long
#define gc getchar
#define R register
using namespace std;
//---------------------初始函数-------------------------------
il int read(){
R int x=0;R bool f=0;R char ch=gc();
while(!isdigit(ch)) {f|=ch=='-';ch=gc();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
return f?-x:x;
}
il int max(int a,int b) {return a>b?a:b;}
il int min(int a,int b) {return a<b?a:b;}
il int abs(int x) {return x>0?x:-x;}
//---------------------初始函数-------------------------------
const int MAXN=1e6+10,INF=0x3f3f3f3f;
int n,a[MAXN],f[MAXN][4];
//a->原数组，f->DP数组，第一维表示下标，第二维表示该下标对应数值+2,f数组记录到下标为i且该下标对应数值+2为j时的最小修改次数
bool hav[MAXN][4];
//hav->能否到达下标为i且该下标对应数值+2为j的状态
signed main(){
n=read();
for(R int i=1;i<=n;++i) a[i]=read();
memset(f,INF,sizeof(f));
f[1][a[1]+2]=0;hav[1][a[1]+2]=1;//初始化
for(R int i=2;i<=n;++i){
if(a[i]==-1){
if(hav[i-1][1]) f[i][1]=f[i-1][1],hav[i][1]=1;
//如果前一下标可以到达值为-1的状态，那就继承前一状态的次数
//如果前一下标可以到达值为0的状态，因为-1+0还是-1,又不满足序列单调不降，所以不改变f数组的值
if(hav[i-1][3]) f[i][3]=f[i-1][3]+2,hav[i][3]=1;
//如果前一下标可以到达值为1的状态，那就可以通过-1+2=1得到这一下标到达值为1的状态的次数
}
else if(a[i]==0){
if(hav[i-1][1]) f[i][1]=f[i-1][1]+1,hav[i][1]=1,f[i][2]=f[i-1][1],hav[i][2]=1;
//如果前一下标可以到达值为-1的状态，那就可以通过0+（-1）=-1得到这一下标到达值为-1的状态的次数，继承前一下标到达-1时状态得到这一下标到达值为0的状态的次数（显然满足单调不降）
if(hav[i-1][2]) f[i][2]=min(f[i][2],f[i-1][2]),hav[i][2]=1;
//如果前一下标可以到达值为0的状态，那就继承前一状态的次数（因为可能被第一条if改过f[i][2]，所以取最小值）
if(hav[i-1][3]) f[i][3]=f[i-1][3]+1,hav[i][3]=1;
//如果前一下标可以到达值为1的状态，那就可以通过0+1=1得到这一下标到达值为1的状态的次数
}
else if(a[i]==1){
if(hav[i-1][1]) f[i][1]=f[i-1][1]+2,hav[i][1]=1,f[i][2]=f[i-1][1]+1,hav[i][2]=1,f[i][3]=f[i-1][1],hav[i][3]=1;
//如果前一下标可以到达值为-1的状态，那就可以通过1+（-2）=-1得到这一下标到达值为-1的状态的次数，通过1+（-1）=0得到这一下标到达值为0的状态的次数，继承前一下标到达-1时状态得到这一下标到达值为1的状态的次数（显然满足单调不降）
if(hav[i-1][2]) f[i][3]=min(f[i][3],f[i-1][2]),hav[i][3]=1;
//如果前一下标可以到达值为0的状态，继承前一下标到达0时状态得到这一下标到达值为1的状态的次数（显然满足单调不降）
if(hav[i-1][3]) f[i][3]=min(f[i][3],f[i-1][3]),hav[i][3]=1;
//如果前一下标可以到达值为1的状态，那就继承前一状态的次数
}
}
if(!hav[n][1]&&!hav[n][2]&&!hav[n][3]) printf("BRAK");
//都到不了下标为n的状态，就是无解
else printf("%d",min(f[n][1],min(f[n][2],f[n][3])));
return 0;
}2.只用
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#define il inline
#define ll long long
#define gc getchar
#define R register
using namespace std;
//---------------------初始函数-------------------------------
il int read(){
R int x=0;R bool f=0;R char ch=gc();
while(!isdigit(ch)) {f|=ch=='-';ch=gc();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
return f?-x:x;
}
il int max(int a,int b) {return a>b?a:b;}
il int min(int a,int b) {return a<b?a:b;}
il int abs(int x) {return x>0?x:-x;}
//---------------------初始函数-------------------------------
const int MAXN=1e6+10,INF=0x3f3f3f3f;
int n,a[MAXN],f[MAXN][4];
bool hav[MAXN];
signed main(){
n=read();
for(R int i=1;i<=n;++i) a[i]=read();
memset(f,INF,sizeof(f));
f[1][a[1]+2]=0;
for(R int i=2;i<=n;++i){
if(a[i]==-1){
if(f[i-1][1]!=INF) f[i][1]=f[i-1][1];
if(f[i-1][3]!=INF) f[i][3]=f[i-1][3]+2;
}
if(a[i]==0){
if(f[i-1][1]!=INF) f[i][1]=f[i-1][1]+1,f[i][2]=f[i-1][1];
if(f[i-1][2]!=INF) f[i][2]=min(f[i][2],f[i-1][2]);
if(f[i-1][3]!=INF) f[i][3]=f[i-1][3]+1;
}
if(a[i]==1){
if(f[i-1][1]!=INF) f[i][1]=f[i-1][1]+2,f[i][2]=f[i-1][1]+1,f[i][3]=f[i-1][1];
if(f[i-1][2]!=INF) f[i][3]=min(f[i][3],f[i-1][2]);
if(f[i-1][3]!=INF) f[i][3]=min(f[i][3],f[i-1][3]);
}
}
int ans=min(f[n][1],min(f[n][2],f[n][3]));
if(ans>=INF) printf("BRAK");
else printf("%d",ans);
return 0;
}当然，由于个人码风习惯，我更喜欢用
4.后记
这里还有个小问题，可以帮大家加深对DP的理解。
Q1:为什么其他题解都要判定a[i] 的值，而你不判。
例子：
当
A1:这一步操作是在开始DP前进行的，相当于在DP开始前修改a[i] 的值，而我的代码是在DP过程中随用随改，并不兼容在DP开始前修改a[i] 的方式。
如果还有问题欢迎私信，好的问题会挂出来帮助其他OIer进行理解