洛谷 P3558 分析（别看）

科技起源的小号1

2026-10-02 16:31:13

发布于：天津

4阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：操作次数的最小值

1.2 题目背景、允许、禁止与限制

背景：有一个长度为 $n$ 的只含 $-1,0,1$ 三种数字序列x
允许：每次操作可将 $x_{i+1}$ 变为 $x_{i+1}+x_i$ ，对于每个 $x_i$ 都可以是无限大的数字
禁止：
限制：最终要求将整个序列变为非递减序列

1.3 题目数据范围与猜测

$1 \le n \le 1000000 \longrightarrow O(n)$

1.4 一句话概括题意

在一个序列中进行操作，每次操作可以使 $x_{i+1}$ 变为 $x_{i+1}+x_i$ ，求这个序列转化为非递减序列所需的最小操作次数

2 题目破题推导

2.1 第一步：分情况讨论与数学计算结合

当前这位如果是 $-1$ ，要想变成 $1$ ，必须要前一位是 $1$ 的情况下操作两次；要想变成 $-1$ ，不用操作；而无论用什么方式，都无法使 $-1$ 变成 $0$
为什么说无论用什么方式，都无法使 $-1$ 变成 $0$ ，因为这题中有个要求是“非递减”。要使 $-1$ 变成 $0$ ，就必须要这一项之前是 $1$ ，但如果这一项之前是 $1$ ，这一项是 $0$ ，就不满足非递减了，因此不考虑这种方案
当前这位如果是 $0$ ，要想变成 $1$ ，必须要前一位是 $1$ 的情况下操作一次；要想变成 $-1$ ，必须要前一位是 $-1$ 的情况下操作一次；而要想变成 $0$ 则无需操作
当前这位如果是 $1$ ，要想变成 $-1$ ，必须要前一位是 $-1$ 的情况下操作两次；要想变成 $1$ ，不用操作；而要想变成 $0$ ，必须是前一项是 $-1$ 的情况下操作1次

3 模型匹配

先提取关键词：前面的操作影响后面的结果、只和特定的几位有关系、求满足条件下的最小值
那不用说了，一定是 $\huge{动态规划}$

4 具体方案

4.1 动态规划定义（重点）

首先，先建立 dp 数组
设置 $dp_i$ 表示以 $i$ 为结尾时，使序列符合条件所需的最小操作次数
但是出现了问题，我们无法确定当前考虑的这一项是什么，无法推导，因此考虑扩维
定义 $dp[i][k](0 \le k \le 2)$ 表示以 $i$ 为结尾时并且当前这个位置的数字是 $k-1$ 时，使序列符合条件所需的最小操作次数

4.2 初始化

求最大值，所以dp数组每一项都设为小值，除了 $dp[i][a[1] + 1]$ 设置为极大值

4.3 状态转移方程

我们的定义清晰了，合法方案也清晰了，因此直接就是（懒得打latex数学公式了）

for (int i = 2;i <= n;i++){
	if (a[i] == 1){
		dp[i][0] = dp[i - 1][0] + 2;
		dp[i][1] = dp[i - 1][0] + 1;
		dp[i][2] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
	} else if (a[i] == 0){
		dp[i][0] = dp[i - 1][0] + 1;
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]);
		dp[i][2] = dp[i - 1][2] + 1;
	} else {
		dp[i][0] = dp[i - 1][0];
		dp[i][2] = dp[i - 1][2] + 2;
	}
}

4.4 答案求取

由于这题如果没有方案就输出BARK，那么就判断一下 $dp[i][1/2/3]$ 是否都是最大值
是输出 BARK，不是输出其中最小值

5 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 1111111;
int a[N];
int dp[N][3];

int main(){
	
	cin >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[1][a[1] + 1] = 0;
	for (int i = 2;i <= n;i++){
		if (a[i] == 1){
			dp[i][0] = dp[i - 1][0] + 2;
			dp[i][1] = dp[i - 1][0] + 1;
			dp[i][2] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
		} else if (a[i] == 0){
			dp[i][0] = dp[i - 1][0] + 1;
			dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]);
			dp[i][2] = dp[i - 1][2] + 1;
		} else {
			dp[i][0] = dp[i - 1][0];
			dp[i][2] = dp[i - 1][2] + 2;
		}
	}
	if (min({dp[n][0],dp[n][1],dp[n][2]}) == dp[0][0]){
		cout << "BRAK";
		return 0;
	}
	cout << min({dp[n][0], dp[n][1], dp[n][2]});
	
	return 0;
}