动态规划·朴素 DP 思路引导
WaterSky
·
·
算法·理论
前言：
不知道各位有没有这样的想法，就是在碰到一道题，感觉它很像 DP，也确实是 DP，但却死活不会设计状态，设计出的状态也不会转移，出考场才发现原来状态那么简单，或者是自己之前 Pass 掉的做法。
我一直都有这样的困惑，所以写了一些记录，有时候状态的设计是靠经验和直觉，也有时候是根据推理得出的。
这部分记录是朴素 DP，不经过优化的思路引导，并不权威，只是分享自己的记录，也希望对各位有帮助。如果有漏的，出错的地方，希望各位 直接指出，谢谢 QAQ。
优化 DP 基本是建立在朴素 DP 设计好，然后根据一些套路 / 状态转移过程种需要优化的地方使用一些 数据结构 如线段树，单调队列等进行优化，又或者是根据一些性质进行决策优化等等，在这里不展开，如果有机会我会再开一篇专栏写。
我会放一些关于 DP 的一些基础，然后放几道我感觉有引导性的题目，和题解不同的是，我会注重思考的过程，而非算法本身。
推荐题单：
- 【动态规划】普及\~ 省选的 dp 题
- 能力提升综合题单 Part4 动态规划 1
动态规划
这部分主要是给出一些动态规划的基础，让思考有个底，不然没有目的的思考相当于边发呆边等灵感。
不带什么引入了，觉得生硬受着。
DP 既指拆分为子问题，通过子问题最优策略转移为整体问题最优策略得出结果的算法过程，也指分阶段思考，阶段性转移的思想。
需要满足的条件是：
- 无后效性。设立的状态的决策不会受到之前决策的选择影响。
- 最优化原理。可以拆分为若干个子问题，每个子问题的最优即为整体问题的最优。
那么当我们设计一个状态时，就需要思考这两个条件，如果成立，那么再思考状态的缩减 / 具体的转移。否则先思考能否通过添加一些状态的描述使条件满足，或者转移的时候将后续可计算的影响直接统计，不然就直接推翻，不要去想着在状态转移里分类讨论，如果是分类讨论可以解决的事情，那么添加状态描述一定可以，否则就是一个深坑，只会白白浪费时间。
状态的设计前人也总结了算法框架，并做了分类，所以我们思考就可以根据分类应用的限制缩小思考范围，减小时间成本。
背包问题
一类 DP 问题，通常有价值和体积的限制，或者需要将问题转换为背包适用的模型，数据范围视情况而定。
分类有：01 背包，完全背包，分组背包，多重背包等，也可以应用到树上，成为树上背包。
区间 DP
可以通过子区间转换为整体，通常以区间左右端点位置为状态，以区间长度为阶段性转移，常见适用数据范围为 N \le 10^4。
常见题型是合并操作，或者是，移动拾取一些奇怪的东西等，当然还有别的，别被局限住了。常见的套路是断环成链，应用于首尾相接的情况。
状压 DP
用当前状态转换为任意进制数字表示，并作为 DP 状态，通常数据范围较小，N \le 25。当然有时候题面会藏起来实际的状态和其范围使它不那么像状压，所以要留个心眼。
在棋盘上也有按格转移的插头 DP。
数位 DP
对于数进行转移，比较数学，同样数据范围视情况而定。
树型 DP
比较重要的 DP，在树上进行 DP，两种常用模型是树上背包，换根 DP，当状态只与深度相关时可以进行长链剖分进行优化。
当给出的是一颗基环树时，常用的操作是找到环，然后将其中一条边单独考虑，然后断掉形成一颗树，再进行 DP。
图上 DP
在图上根据拓扑序进行转移，如果是有向带环图，则需要进行缩点。
的题目
打乱顺序放几道我在这段时间里刷到的一些比较舒服的 DP 题目，或者两三年前扔在做题计划被我想起来的题目。
原题会放在最后面。
分别会有：
- 启示：给一些没有思路的同学一些启发。
- 答案：在提示折叠框中，作为启示的答案。
- Solution.：作为整道题目的答案与讲解。
- Code.：在讲解中，作为题目的正确答案，会提供注释。
T1
题目描述：
给出一颗以 0 为根节点的有根树，点有点权 v 与颜色，边有边权 d，一开始除了根节点是白色，其他的节点都是黑色。\
定义：一个黑色节点的代价为此节点到达祖先中最近的白色节点的距离 \times 此点权。一个白色节点的代价为 0。\
可以至多选择 k 个黑色节点进行染色使其变为白色，求最小代价和。
输入：
第 1 行包括两个整数 n 和 k。\
第 2 到 n+1 行每行分别有三个整数。第 i+1 行分别表示第 i 个点的点权，父节点和与父节点的距离。
输出：
一个整数表示最小代价。
输入输出样例 #1
输入 #1
4 2
1 0 1
1 1 10
10 2 5
1 2 3
输出 #1
4
数据范围
:::::info[启示：状态的设立需要推导答案的计算过程。]
思考：\
答案和什么相关？\
对于一个点其自身有什么状态？\
能否通过其设立状态？
::::success[浅层答案]
可以发现，一个点的代价只与最近的祖先位置相关。\
而对于一个点，自身的状态有点的编号和点的颜色。\
而点的颜色数量有其限制。
那么应该如何设计状态？
:::success[答案的本源]
设立状态 $f_{i,j,k,0/1}$ 表示第 $i$ 个节点最近的白色祖先为 $j$，以 $i$ 节点为根的子树内有 $k$ 个白色节点，且第 $i$ 个节点的颜色为 $0/1$ 时，其子树的最小代价。
嗯，很完美的状态，那么，**转移**呢？
:::
::::
:::::
:::::info[启示：状态的转移需要拆分贡献的相互联系。]
思考：\
每一个节点的状态与其子节点的状态有什么关联？\
答案的计算是否与这种联系直接相关？
::::success[浅层答案]
当这个节点为白色时，子节点的最近白色祖先就是这个节点。\
如果这个节点不是，那么子节点与此节点的最近白色祖先相同。
那么应该如何转移？
:::success[答案的本源]
推导出以上，答案就呼之欲出了，显然就是一个变形的树上背包，具体转移看代码：
```cpp
void dp(long long u){
stac[++tot]=u;//使用栈处理祖先
for(int i=head[u];i;i=e[i].nxt){//逐个遍历
int v=e[i].to;
dep[v]=dep[u] + e[i].w,dp(v);
for(int j=1;j<=tot;j++)
for(int k=K;k>=0;k--){
f[u][stac[j]][k][0]+=f[v][stac[j]][0][0],
f[u][stac[j]][k][1]+=f[v][u][0][0];
for(int l=1;l<=k;l++)
f[u][stac[j]][k][0]=
min(f[u][stac[j]][k][0],f[v][stac[j]][l][0]+f[u][stac[j]][k-l][0]),
f[u][stac[j]][k][1]=
min(f[u][stac[j]][k][1],f[v][u][l][0]+f[u][stac[j]][k-l][1]);
//我尽量让它好看点了，但是太长，自动换行看起来很丑，我就只能加上一些手动换行了。
}
}
for(int i=1;i<=tot;i++){//背包
for(int j=K;j>=1;j--)
f[u][stac[i]][j][0]=
min(f[u][stac[i]][j][0]+w[u]*(dep[u]-dep[stac[i]]),f[u][stac[i]][j-1][1]);
f[u][stac[i]][0][0]+=w[u] * (dep[u]-dep[stac[i]]);
}
tot --;
}
```
:::
那么，如何求解最终答案？
::::
:::::
::::info[启示：状态的答案需要回溯推理的本质含义。]
思考：\
回归题目。\
回归状态的设计和具体意思？\
怎么使用状态表示最终答案？
:::success[答案的本源]
显而易见，因为根节点本身为白色，且 $k$ 个机会全部使用肯定更优，那么答案就是当根节点，无最近白色公共祖先，子树内有 $k$ 个白色节点，且自身为白色节点时的最优解。
:::
::::
::::info[Solotion. 所有伟大源于细节]
在做这道题前，我做了另一道很相似的树上背包，但是和这道题不同的是，当前状态与祖先并没有直接相关。因此我带入思维惯性，设计了一个缺少祖先影响的状态而耗费时间很久，最后才反应过来。
不妨总结一下这道题的思路流程：
首先，我们先判断出这道题是一道 DP 题：\
暂时没有显然的贪心策略且树本身带有很强的子结构。
然后，我们设立状态：分析答案的计算过程，然后带入状态设计，最终发现是变形树上背包。
接着转移，思考自身状态与子状态之间的联系。
最后回归答案，试着用状态表示最终的答案。
结束。
:::success[Code.]
```
#include<bits/stdc++.h>
using namespace std;
long long n,K;
struct wbx{
int nxt,to,w;
}e[100005];
long long head[1000005],cnt;
long long w[1000005];
long long f[105][105][55][2];
long long dep[105];
long long stac[105],tot;
void add(long long x,long long y,long long w){
e[++cnt]={head[x],y,w},head[x]=cnt;
}
void dp(long long u){
stac[++tot]=u;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
dep[v]=dep[u]+e[i].w;
dp(v);
for(int j=1;j<=tot;j++)
for(int k=K;k>=0;k--){
f[u][stac[j]][k][0]+=f[v][stac[j]][0][0];
f[u][stac[j]][k][1]+=f[v][u][0][0];
for(int l=1;l<=k;l++){
f[u][stac[j]][k][0]=
min(f[u][stac[j]][k][0],f[v][stac[j]][l][0]+f[u][stac[j]][k-l][0]);
f[u][stac[j]][k][1]=
min(f[u][stac[j]][k][1],f[v][u][l][0]+f[u][stac[j]][k-l][1]);
}
}
}
for(int i=1;i<=tot;i++){
for(int j=K;j>=1;j--)
f[u][stac[i]][j][0]=
min(f[u][stac[i]][j][0]+w[u]*(dep[u]-dep[stac[i]]),f[u][stac[i]][j-1][1]);
f[u][stac[i]][0][0]+=w[u]*(dep[u]-dep[stac[i]]);
}
tot--;
}
int main()
{
cin>>n>>K;
for(int i=1;i<=n;i++){
int x,y,z;
cin>>w[i]>>y>>z;
add(y,i,z);
}
dp(0);
cout<<f[0][0][K][0];
return 0;
}
```
:::
::::
### T2
#### 题目描述
给出一个 $n$ 个点，$m$ 条边的无向图。可以选择一个点作为起点 $r$，求选择一些边使无向图联通的最小总代价。\
定义 $u$ 到 $v$ 的代价为 $r$ 到 $u$ 路径上的点数 $\times$ 边权。
#### 输入格式
第一行两个用空格分离的正整数 $n,m$。\
接下来 $m$ 行，每行三个用空格分离的正整数，表示一条边的两个端点与边权。
#### 输出格式
一个正整数，表示最小的总代价。
#### 输入输出样例 #1
##### 输入 #1
```
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
```
##### 输出 #1
```
4
```
#### 输入输出样例 #2
##### 输入 #2
```
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2
```
##### 输出 #2
```
5
```
【数据规模与约定】\
对于 $20\%$ 的数据： 保证输入是一棵树，$1 \le n \le 8$，$v \le 5\times 10^3$ 且所有的 $v$ 都相等。\
对于 $40\%$ 的数据：$1 \le n \le 8$，$0 \le m \le 10^3$，$v \le 5\times 10^3$ 且所有的 $v$ 都相等。\
对于 $70\%$ 的数据：$1 \le n \le 8$，$0 \le m \le 10^3$，$v \le 5\times 10^3$。\
对于 $100\%$ 的数据：$1 \le n \le 12$，$0 \le m \le 10^3$，$v \le 5\times 10^5$。
:::::info[启示：性质有提示]
保证输入是一棵树？\
为什么要这样说？
::::success[浅层答案]
容易发现，答案必定是一颗树，那么与代价的计算相关。
:::success[答案的本源]
代价的计算为深度 $\times$ 边权。
:::
::::
:::::
:::::info[启示：数据有异常]
$n$ 这么小，对于做法有什么提示？\
符合哪种类型的 DP？
::::success[浅层答案]
状压。状态怎解？
:::success[答案的本源]
设立状态：$f_{i,j}$ 表示每个节点是否选择的状态为 $i$，且到达第 $j$ 层的最小代价和。
那么我们可以直接枚举子集并进行转移。
:::
::::
:::::
::::info[Solution. 宇宙有天才]
这题的思维难度不算很大，所以启示写这么少，也是为了引导一下思考的正确性。
思考下我们从这道题中得到了什么？看一下给出的特殊性质，通常都是一些提示，然后再联系题目，最终敲定答案。
时间复杂度的计算可以自己计算，简单且繁琐的东西我就不搞了。
需要注意一下重边的情况。
:::success[Code.]
```
#include<bits/stdc++.h>
using namespace std;
long long n,m;
struct wbx{
long long to,nxt,w;
}e[5005],Fzy[5005];
long long head[10005],cnt;
void add(long long x,long long y,long long w){
e[++cnt]={y,head[x],w},head[x]=cnt;
}
long long f[1<<16][20];
long long ans=1e12;
void dfs(long long x,long long num){
long long s[20],y=0;
memset(s,0x3f3f,sizeof(s));
set<long long>son;
for(int i=0;i<n;i++){
if(x&(1<<i)) for(int j=head[i];j;j=e[j].nxt)
if(!(x&(1<<e[j].to)))
s[e[j].to]=min(s[e[j].to],num*e[j].w),
son.insert(e[j].to);
}
for(int i=1;i<(1<<son.size());i++){//枚举子集
int y=0,w=0,j=0;
for(auto v:son){
if(i&(1<<j)) y|=(1<<v),w+=s[v];
j++;
}
if(f[x][num]+w<f[x|y][num+1])
f[x|y][num+1]=f[x][num]+w,dfs(x|y,num+1);
}
if(x==(1<<n)-1) ans=min(ans,f[x][num]);
}
bool cmp(wbx x,wbx y){
if(x.nxt!=y.nxt) return x.nxt<y.nxt;
if(x.to!=y.to) return x.to<y.to;
return x.w<y.w;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,v;
cin>>x>>y>>v,Fzy[i]={x-1,y-1,v};
}
sort(Fzy+1,Fzy+1+m,cmp);
for(int i=1;i<=m;i++){//去重边
if(Fzy[i].to==Fzy[i-1].to && Fzy[i].nxt==Fzy[i-1].nxt) continue;
add(Fzy[i].to,Fzy[i].nxt,Fzy[i].w);
add(Fzy[i].nxt,Fzy[i].to,Fzy[i].w);
}
for(int i=0;i<=(1<<n);i++)
for(int j=2;j<=n;j++)
f[i][j]=1e12;
for(int i=0;i<n;i++)
dfs(1<<i,1);//枚举每一个节点作为起点
cout<<ans;
return 0;
}
```
:::
::::
### T3
原谅我真的不会简化题意。
#### 题目描述
将大海近似的看做 $x$ 轴建立一个竖直的平面直角坐标系，你所在的初始位置在 $x$ 轴上。
一开始空中有 $N$ 个彩蛋，对于第 $i$ 个彩蛋，他的初始位置用整数坐标 $(x_{i}, y_{i})$ 表示，游戏开始后，它匀速沿 $y$ 轴负方向下落，速度为 $v_{i}$ 单位距离 / 单位时间。你的初始位置为 $(x_{0}, 0)$，你可以沿 $x$ 轴的正方向或负方向移动，你的移动速度是 $1$ 单位距离 / 单位时间，使用秘密武器得到一个彩蛋是瞬间的，得分为当前彩蛋的 $y$ 坐标的千分之一。\
求在收集到所有彩蛋的基础上，得到的分数最高。
#### 输入格式
第一行为两个整数 $N$，$x_{0}$ 用一个空格分隔，表示彩蛋个数与你的初始位置。
第二行为 $N$ 个整数 $x_{i}$，每两个数用一个空格分隔，第 $i$ 个数表示第 $i$ 个彩蛋的初始横坐标。\
第三行为 $N$ 个整数 $y_{i}$，每两个数用一个空格分隔，第 $i$ 个数表示第 $i$ 个彩蛋的初始纵坐标。\
第四行为 $N$ 个整数 $v_{i}$，每两个数用一个空格分隔，第 $i$ 个数表示第 $i$ 个彩蛋匀速沿 $y$ 轴负方向下落的的速度。
#### 输出格式
一个实数，保留三位小数，为收集所有彩蛋的基础上，可以得到最高的分数。
#### 输入输出样例 #1
##### 输入 #1
```
3 0
-4 -2 2
22 30 26
1 9 8
```
##### 输出 #1
```
0.000
```
#### 说明 / 提示
对于 $30\%$ 的数据，$N\leq 20$。
对于 $60\%$ 的数据，$N\leq 100$。
对于 $100\%$ 的数据，$-10^4 \leq x_{i},y_{i} \leq 10^4$，$0\leq v_{i} \leq 10^4$，$N \leq 1000$。
:::::info[启示：答案藏于过往的罅隙]
看到题面，有没有让你想起一些类型？\
根据经验，状态应该如何设计？
::::success[浅层答案]
区间 DP。
:::success[答案的本源]
设计状态 $f_{i,j},g_{i,j}$ 分别表示将 $i,j$ 收集后位置在 $i,j$。
啊？不是有后效性吗？
:::
::::
:::::
:::::info[启示：未来的答案当前敲定]
别慌，回看前面动态规划基础给出的应对策略。
::::success[浅层答案]
因为当前耗费的时间对剩余彩蛋所造成的影响是可计算的。
:::success[答案的本源]
减去此次移动使用时间所造成的损失。
:::
::::
:::::
::::info[Solution. 而现在的答案…]
比较套路化的题目，在考前做几道这种题积累一下常见 trick 有奇效。
:::success[Code.]
```
#include<bits/stdc++.h>
using namespace std;
long long n,x0;
long long sum;
long long s[1000005];
struct wbx{
long long x,y,v;
}a[1000005];
bool cmp(wbx x,wbx y){return x.x<y.x;}
long long f[1005][1005],g[1005][1005];
long long Fzy(long long l,long long r){return s[n]-s[r]+s[l-1];}
int main(){
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
cin>>n>>x0;
for(int i=1;i<=n;i++) cin>>a[i].x;
for(int i=1;i<=n;i++) cin>>a[i].y,sum+=a[i].y;
for(int i=1;i<=n;i++) cin>>a[i].v;
a[++n].x=x0,a[n].v=0;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].v;
for(int i=1;i<=n;i++)
if(a[i].y==0 && a[i].x==x0 && a[i].v==0)
f[i][i]=0,g[i][i]=0;
for(int len=2;len<=n;len++)
for(int l=1,r=len;r<=n;l++,r++){
f[l][r]=min(f[l][r],f[l+1][r]+Fzy(l+1,r)*(a[l+1].x-a[l].x));
f[l][r]=min(f[l][r],g[l+1][r]+Fzy(l+1,r)*(a[r].x-a[l].x));
g[l][r]=min(g[l][r],g[l][r-1]+Fzy(l,r-1)*(a[r].x-a[r-1].x));
g[l][r]=min(g[l][r],f[l][r-1]+Fzy(l,r-1)*(a[r].x-a[l].x));
}
printf("%.3f",(sum-min(f[1][n],g[1][n]))/1000.0);
return 0;
}
```
:::
::::
### T4
拿道清新题作为结尾。
#### 题目描述
给定一个由集合 $\{-1, 0, 1\}$ 中的 $n$ 个整数 $x_1, x_2,\cdots, x_n$ 组成的序列。字节计算机是一种允许对序列进行以下操作的设备：对于任何 $1 \leq i < n$，可以将 $x_{i+1}$ 改为 $x_{i+1} + x_i$。字节计算机可以存储的整数范围没有限制，即每个 $x_i$ 可以（原则上）具有任意小或大的值。
编程实现字节计算机，使其将输入序列转换为非递减序列（即 $x_1 \leq x_2 \leq \cdots \leq x_n$），并使操作次数最少。
#### 输入格式
标准输入的第一行包含一个整数 $n$($1 \leq n \leq 1000000$)，表示（字节计算机的）输入序列中的元素个数。\
第二行包含 $n$ 个整数 $x_1, x_2, \cdots, x_n$ ($x_i \in \{-1, 0, 1\}$)，它们是（字节计算机的）输入序列的连续元素，元素之间用单个空格分隔。
#### 输出格式
标准输出的第一行应输出一个整数，即字节计算机必须执行的最小操作次数，以使其输入序列成为非递减序列；如果无法获得这样的序列，则输出单词 BRAK（波兰语，意为“无”）。
#### 输入输出样例 #1
##### 输入 #1
```
6
-1 1 0 -1 0 1
```
##### 输出 #1
```
3
```
::::info[Solution. 嗯]
比较简单的题目，所以不放启示了。
首先明确，最优时转换的数只能为 $-1,0,1$。
然后美美分类讨论。
先看数据范围：$n (1≤n≤1000000)$。
那么这题只能 $O(n)$ 了。
要么贪心要么 DP。
贪心要简单一些，但是这里只写 DP。
设计 DP 的状态，先想一个问题：怎样的操作 / 状态会影响到子问题的状态？
首先，位置肯定有：设 $i$ 表示第 $i$ 位置的元素。
其次，元素的具体数值也很有用，而元素自身的范围也暗示了这点：$(x_i ∈\{−1,0,1\})$。
设 $j\in \{-1,0,1\}$ 表示操作后该元素的大小 / 不操作。
状态设计到这就可以了，但是我一开始没意识到操作和不操作可以合并，后面也不想改了：
- $j=1$：操作，操作后为 $1$ 的最少操作数。
- $j=2$：不操作的最少操作数。
- $j=3$：操作，操作后为 $0$ 的最少操作数。
- $j=4$：操作，操作后为 $-1$ 的最少操作数。
思考状态如何转移。
- 第 $i$ 个元素本身为 $-1$。
- $j=1$，$+2$。
- 前一个元素变为 $1$。
- 前一个元素本身为 $1$ 且不操作。
- $j=2$，$+0$。
- 前一个元素变为 $-1$。
- 前一个元素本身为 $-1$ 且不操作。
- $j=3$，$+1$。
- 前一个元素变为 $1$。
- 前一个元素本身为 $1$ 且不操作。
- $j=4$，$/$。
- 第 $i$ 个元素本身为 $0$。
- $j=1$，$+1$。
- 前一个元素变为 $1$。
- 前一个元素本身为 $1$ 且不操作。
- $j=2$，$+0$。
- 前一个元素变为 $-1$。
- 前一个元素变为 $0$。
- 前一个元素本身为 $-1$ 且不操作。
- 前一个元素本身为 $0$ 且不操作。
- $j=3$，$/$。
- $j=4$，$+1$。
- 前一个元素变为 $-1$。
- 前一个元素本身为 $-1$ 且不操作。
- 第 $i$ 个元素本身为 $1$。
- $j=1$，$/$。
- $j=2$，$+0$。
- 前一个元素变为 $1$。
- 前一个元素本身为 $1$ 且不操作。
- 前一个元素变为 $0$。
- 前一个元素本身为 $0$ 且不操作。
- 前一个元素变为 $-1$。
- 前一个元素本身为 $-1$ 且不操作。
- $j=3$，$+1$。
- 前一个元素变为 $-1$。
- 前一个元素本身为 $-1$ 且不操作。
- $j=4$，$+2$。
- 前一个元素变为 $-1$。
- 前一个元素本身为 $-1$ 且不操作。
考虑边界状态，当 $i=1$ 时只能不操作，且操作数为 $0$。
:::success[Code.]
```
#include<bits/stdc++.h>
using namespace std;
long long n;
long long x[1000005];
long long f[1000005][5];
//1 换 变为1
//2 不换
//3 换，变为 0
//4 换，变为-1
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>x[i];
f[1][1]=1e8,f[1][3]=1e8,f[1][4]=1e8;
for(int i=2;i<=n;i++){
if(x[i]==1){
if(x[i-1]==-1) f[i][3]=f[i-1][2]+1,f[i][4]=f[i-1][2]+2;
else f[i][3]=f[i][4]=1e8;
f[i][3]=min(f[i][3],f[i-1][4]+1);
f[i][4]=min(f[i][4],f[i-1][4]+2);
f[i][2]=min(f[i-1][1],min(f[i-1][2],min(f[i-1][3],f[i-1][4])));
f[i][1]=1e8;
}
if(x[i]==0){
if(x[i-1]==-1) f[i][4]=f[i-1][2]+1;
else f[i][4]=1e8;
f[i][4]=min(f[i][4],f[i-1][4]+1);
f[i][3]=1e8;
if(x[i-1]==1) f[i][1]=f[i-1][2]+1;
else f[i][1]=1e8;
f[i][1]=min(f[i][1],f[i-1][1]+1);
if(x[i-1]<=0) f[i][2]=f[i-1][2];
else f[i][2]=1e8;
f[i][2]=min(f[i][2],min(f[i-1][3],f[i-1][4]));
}
if(x[i]==-1){
if(x[i-1]==1) f[i][1]=f[i-1][2]+2,f[i][3]=f[i-1][2]+1;
else f[i][1]=f[i][3]=1e8;
f[i][3]=1e8;
f[i][1]=min(f[i][1],f[i-1][1]+2);
if(x[i-1]==-1) f[i][2]=f[i-1][2];
else f[i][2]=1e8;
f[i][2]=min(f[i][2],f[i-1][4]);
f[i][4]=1e8;
}
}
if(min(f[n][1],min(f[n][2],min(f[n][3],f[n][4])))==1e8) cout<<"BRAK";
else cout<<min(f[n][1],min(f[n][2],min(f[n][3],f[n][4])));
return 0;
}
```
:::
::::
### 原题：
[T1](https://www.luogu.com.cn/problem/P3354) [T2](https://www.luogu.com.cn/problem/P3959) [T3](https://www.luogu.com.cn/problem/P2466) [T4](https://www.luogu.com.cn/problem/P3558)。