原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：操作次数的最小值
1.2 题目背景、允许、禁止与限制
背景：有一个长度为 nnn 的只含 −1,0,1-1,0,1−1,0,1 三种数字序列x
允许：每次操作可将 xi+1x_{i+1}xi+1 变为 xi+1+xix_{i+1}+x_ixi+1 +xi ，对于每个 xix_ixi 都可以是无限大的数字
禁止：
限制：最终要求将整个序列变为非递减序列
1.3 题目数据范围与猜测
1≤n≤1000000⟶O(n)1 \le n \le 1000000 \longrightarrow O(n)1≤n≤1000000⟶O(n)
1.4 一句话概括题意
在一个序列中进行操作，每次操作可以使 xi+1x_{i+1}xi+1 变为 xi+1+xix_{i+1}+x_ixi+1 +xi ，求这个序列转化为非递减序列所需的最小操作次数
2 题目破题推导
2.1 第一步：分情况讨论与数学计算结合
* 当前这位如果是 −1-1−1，要想变成 111，必须要前一位是 111 的情况下操作两次；要想变成 −1-1−1，不用操作；而无论用什么方式，都无法使 −1-1−1 变成 000
为什么说无论用什么方式，都无法使 −1-1−1 变成 000，因为这题中有个要求是“非递减”。要使 −1-1−1 变成 000，就必须要这一项之前是 111，但如果这一项之前是 111，这一项是 000，就不满足非递减了，因此不考虑这种方案
* 当前这位如果是 000，要想变成 111，必须要前一位是 111 的情况下操作一次；要想变成 −1-1−1，必须要前一位是 −1-1−1 的情况下操作一次；而要想变成 000 则无需操作
* 当前这位如果是 111，要想变成 −1-1−1，必须要前一位是 −1-1−1 的情况下操作两次；要想变成 111，不用操作；而要想变成 000 ，必须是前一项是 −1-1−1 的情况下操作1次
3 模型匹配
先提取关键词：前面的操作影响后面的结果、只和特定的几位有关系、求满足条件下的最小值
那不用说了，一定是 动态规划\huge{动态规划}动态规划
4 具体方案
4.1 动态规划定义（重点）
首先，先建立 dp 数组
设置 dpidp_idpi 表示以 iii 为结尾时，使序列符合条件所需的最小操作次数
但是出现了问题，我们无法确定当前考虑的这一项是什么，无法推导，因此考虑扩维
定义 dp[i][k](0≤k≤2)dp[i][k](0 \le k \le 2)dp[i][k](0≤k≤2) 表示以 iii 为结尾时并且当前这个位置的数字是 k−1k-1k−1 时，使序列符合条件所需的最小操作次数
4.2 初始化
求最大值，所以dp数组每一项都设为小值，除了 dp[i][a[1]+1]dp[i][a[1] + 1]dp[i][a[1]+1] 设置为极大值
4.3 状态转移方程
我们的定义清晰了，合法方案也清晰了，因此直接就是（懒得打latex数学公式了）
4.4 答案求取
由于这题如果没有方案就输出BARK，那么就判断一下 dp[i][1/2/3]dp[i][1/2/3]dp[i][1/2/3] 是否都是最大值
是输出 BARK，不是输出其中最小值
5 最终代码（禁止抄袭，仅用于参考）
错误点：数组开小
注意到题面描述中的 n≤10000n \le 10000n≤10000 只对于 48%48\%48% 的数据，而全部数据的范围实际上是 n≤1000000n \le1000000n≤1000000
