洛谷 P3146 分析（别看）

科技起源

2026-07-06 14:21:42

发布于：河北

5阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：求操作完毕序列中的最大值

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

背景：有一个有 $n$ 个数的序列
允许：选择两个相邻且相等的数，替换为比原数 $+1$ 的数
禁止：
限制：

1.3 题目数据范围与猜测

$2 \le n \le 248 \longrightarrow O(n^3)$

1.4 一句话概括题意

有一个序列，每次可以选择两个相邻且相等的数，替换为比原数 $+1$ 的数。最终求操作完毕后的序列最大值。

2 题目破题推导

注：以下六种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

2.3 以终为始、以始为终

两个相邻的数（这里的一个数不仅包括单独的一个数，更包括一段区间合并后得到的数）能合并
当且仅当：

左右两边都能完成合并
左边合并结果 $=$ 右边合并结果

也就是说，对于一个大区间 $[left,right]$ ，中间枚举断点 $i(left\le i \le right)$ ，区间 $[left,i]$ 和 $[i+1,right]$ （此时假设区间 $[left,i]$ 和 $[i+1,right]$ 均已尝试合并完毕）能合并，当且仅当 $[left,i] = [i+1,right]$ 并且 $[left,i]$ 与 $[i+1,right]$ 均可以合并

2.4 数学

2.5 分情况考虑

2.6 手动推导

2.7 边界测试

3 模型匹配

先提取关键词：时刻求取当前最大值、区间
是 $\huge{区间动态规划}$

4 具体方案

4.1 动态规划定义（重点）

首先，先建立 dp 数组
设置 ${dp_i}_j$ 表示把区间 $[i,j]$ 完全合并成一个数得到的最大值是什么
$0$ 代表区间 $[i,j]$ 无法完全合并

4.2 初始化

求最大值，所以dp数组每一项都设为小值
但是一个数不用合并，因此对于每个 $i (1 \le i \le n)$ ，都要将 ${dp_i}_i$ 设置为 $序列_i$

4.3 状态转移方程

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

for (int len = 2;len <= n;len++){
	for (int left = 1; left + len - 1 <= n;left++){
		int right = left + len - 1;
		for (int i = left;i < right;i++){
			if (dp[left][i] == dp[i + 1][right] && dp[left][i] != 0){
				dp[left][right] = max(dp[left][right], dp[left][i] + 1);
				mx = max(mx, dp[left][right]);
			}
		}
	}
}

4.4 答案求取

对于所有 $i(1 \le i \le n),j(1 \le j \le n) 且 i\le j,求{dp_i}_j$ 的最大值

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

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

const int N = 250;
int dp[N][N];
int n;

int main(){
	
	cin >> n;
	int mx = INT_MIN;
	for (int i = 1;i <= n;i++){
		cin >> dp[i][i];
		mx = max(mx, dp[i][i]);
	}
	for (int len = 2;len <= n;len++){
		for (int left = 1; left + len - 1 <= n;left++){
			int right = left + len - 1;
			for (int i = left;i < right;i++){
				if (dp[left][i] == dp[i + 1][right] && dp[left][i] != 0){
					dp[left][right] = max(dp[left][right], dp[left][i] + 1);
					mx = max(mx, dp[left][right]);
				}
			}
		}
	}
	cout << mx;
	
	return 0;
}