原题链接
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≤10000⟶O(n)或O(nlogn)1 \le n \le 10000 \longrightarrow O(n)或O(nlogn)1≤n≤10000⟶O(n)或O(nlogn)
1.4 一句话概括题意
在一个序列中进行操作，每次操作可以使 xi+1x_{i+1}xi+1 变为 xi+1+xix_{i+1}+x_ixi+1 +xi ，求这个序列转化为非递减序列所需的最小操作次数
2 题目破题推导
> 注：以下六种方法都可以考虑一下
2.1 大拆小、小组大
2.2 正向思维转逆向思维，逆向思维转正向思维
2.3 以终为始、以始为终
2.4 数学
我们要理解一件事情：
当前这位如果是 −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次
2.5 手动推导
2.6 边界测试
3 模型匹配
先提取关键词：前面的操作影响后面的结果、只和特定的几位有关系、求满足条件下的最小值
那不用说了，一定是 动态规划\huge{动态规划}动态规划
4 具体方案
4.1 动态规划定义（重点）
首先，先建立 dp 数组
设置 dpidp_idpi 表示以 iii 为结尾时，使序列符合条件所需的最小操作次数
但是出现了问题，我们无法确定当前考虑的这一项是什么，无法推导，因此考虑扩维
定义 dpijk(0≤k≤2){{dp_i}_j}_k(0 \le k \le 2)dpi j k (0≤k≤2) 表示以 iii 为结尾时并且当前这个位置的数字是 k−1k-1k−1 时，使序列符合条件所需的最小操作次数
4.2 初始化
求最大值，所以dp数组每一项都设为小值，除了 dpix1−1{dp_i}_{x_1-1}dpi x1 −1 设置为极大值
4.3 状态转移方程
我们的定义清晰了，合法方案也清晰了，因此直接就是（懒得打latex数学公式了）
4.4 答案求取
由于这题如果没有方案就输出BARK，那么就判断一下 dpi1/2/3{dp_i}_{1/2/3}dpi 1/2/3 是否都是最大值
是输出 BARK，不是输出其中最小值
5 最终代码（禁止抄袭，仅用于参考）
