洛谷 P1133 分析（别看）

科技起源

2026-07-08 17:49:23

发布于：河北

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

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

背景：需要种 $n$ 棵树，种完树后成环形，每个位置上的树都有一个观赏价值
允许：使得最后种的总价值最高
禁止：
限制：种的每棵树都要比相邻的两个树都高或都低

1.3 题目数据范围与猜测

$4 \le n \le 10^5 \longrightarrow O(n~log~n)$

1.4 一句话概括题意

需要种 $n$ 棵树，种完树后成环形，每个位置上的树都有一个观赏价值。种的每棵树都要比相邻的两个数都高或都低。最后求种树的总价值最高是多少

2 题目破题推导

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

2.1 大拆小、小组大

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

2.3 分情况考虑

2.4 数学

2.5 以终为始、以始为终

2.6 手动推导

只需要理清楚一件事情：
当一棵树高度为 $10$ 时，旁边两棵树只能比它高，可以是 $20$ 或者 $30$
当一棵树高度为 $30$ 时，旁边两棵树只能比它低，可以是 $10$ 或者 $20$
当一棵树高度为 $20$ 时，旁边两棵树可高可低，可以是 $10$ 或者 $30$
额外地，因为这题是“环形”要求，因此还需要时刻转移第 $1$ 棵树的高度并且最终有额外方案判断

2.7 边界测试

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：时刻求取最大值 $\longrightarrow$ $\huge{多维动态规划}$

3.1 需要注意的点

先把dp定义四维，dp[i][j][k][l]代表考虑前 $i$ 棵树，第 $i$ 棵树高度为 $j(0 \le j \le 2)对应着10/20/30$ ，第 $i$ 棵树与它周围的状态为 $k(0 \le k \le 1)对应着高/低$ ，第一棵树的高度为高度为 $j(0 \le j \le 2)对应着10/20/30$
这样所有我们讨论到的点都能包含
那这样其他都很简单了

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

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

int n;
const int N = 1e5 + 10;
int a[N][3];
int dp[N][3][2][3];
/*
dp[i][j][k][l]代表：
考虑前i棵树
最后一棵树高度为j(0/1/2分别代表低中高树)
最后一棵树比它前面的和后面的状态(1代表低,0代表高)
第一棵树的高度为l(0/1/2分别代表低中高树)
时可获得的最大价值 
*/

int main(){
	
	cin >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i][0] >> a[i][1] >> a[i][2];
	}
	// 初始化
	dp[1][0][1][0] = a[1][0];
	dp[1][1][0][1] = a[1][1];
	dp[1][1][1][1] = a[1][1];
	dp[1][2][0][2] = a[1][2];
	// 状态转移
	for (int i = 2;i <= n;i++){
		for (int j = 0;j <= 2;j++){// j循环作用不大，主要用于持续转移dp[][][][l] 
			dp[i][0][1][j] = max(dp[i - 1][1][0][j], dp[i - 1][2][0][j]) + a[i][0];
			dp[i][1][0][j] = dp[i - 1][0][1][j] + a[i][1];
			dp[i][1][1][j] = dp[i - 1][2][0][j] + a[i][1];
			dp[i][2][0][j] = max(dp[i - 1][1][1][j], dp[i - 1][0][1][j]) + a[i][2];
		}
	}
	// 得到结果（只考虑合法状态（环形要求！）） 
	int mx = max({dp[n][0][1][1], dp[n][0][1][2], dp[n][1][0][0], dp[n][1][1][2], dp[n][2][0][1], dp[n][2][0][0]});
	cout << mx;
	
	return 0;
}