博客广场/ 陈俊霖

比赛总结

8月Day2

A.Mortal Kombat Tower 核心思路这是一道经典的动态规划题。游戏规则是两人轮流行动，朋友先手。朋友面对困难 Boss（值为 1）时必须消耗跳过点，而你可以直接击败任意 Boss。我们需要最小化朋友使用的跳过点总数。由于每次行动可以击败 1 或 2 个 Boss，且行动者交替，我们只需记录当前轮到谁（朋友或你）以及当前已经消耗的跳过点数，

陈俊霖发布于 2026-8-8 21:00:21

综合/比赛总结动态规划综合/题解

A.Mortal Kombat Tower

核心思路

这是一道经典的动态规划题。游戏规则是两人轮流行动，朋友先手。朋友面对困难 Boss（值为 1）时必须消耗跳过点，而你可以直接击败任意 Boss。我们需要最小化朋友使用的跳过点总数。

由于每次行动可以击败 1 或 2 个 Boss，且行动者交替，我们只需记录当前轮到谁（朋友或你）以及当前已经消耗的跳过点数，进行 DP 转移即可。

具体步骤

定义状态
- 设 dp[i][0] 表示击败前 i 个 Boss，且下一个该你行动时，朋友已使用的最少跳过点数。
- 设 dp[i][1] 表示击败前 i 个 Boss，且下一个该朋友行动时，朋友已使用的最少跳过点数。
初始化
- 还没有击败任何 Boss 时，下一回合由朋友开始，故 dp[0][1] = 0（表示轮到朋友，跳过点数为 0）。
- 但代码中初始化为 dp[0][0] = 0，这其实表示轮到“你”行动，但朋友还没行动？这里代码可能将 0 定义为你，1 定义为朋友。
  - 仔细看：初始 dp[0][0] = 0，其中 0 表示下一个行动者是“你”。然而第一回合实际是朋友，所以代码中的下标与通常理解相反。
  - 通过转移可以看出：当状态是 dp[i][0]（你行动）时，朋友已经打完上一轮，此时消耗的跳过点数已经计入。接下来你行动，你不需要跳过点。
  - 当状态是 dp[i][1]（朋友行动）时，朋友会消耗跳过点。所以初始设为朋友行动更自然，但代码选择另一种约定，依然正确，只要转移对应。
转移
- 如果当前轮到“你”（状态 dp[i][0]）：
  - 你可以打 1 个 Boss，然后轮到朋友，状态变为 dp[i+1][1]，跳过点不变。
  - 你也可以打 2 个 Boss（如果 i+2 ≤ n），状态变为 dp[i+2][1]，跳过点不变。
- 如果当前轮到“朋友”（状态 dp[i][1]）：
  - 朋友打 1 个 Boss，若该 Boss 困难则消耗 1 跳过点，状态变为 dp[i+1][0]，跳过点增加 a[i]。
  - 若打 2 个 Boss，状态变为 dp[i+2][0]，跳过点增加 a[i] + a[i+1]。
答案
- 击败所有 n 个 Boss 后，无论轮到谁，取 min(dp[n][0], dp[n][1]) 即为最少跳过点。

题解

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

const int INF = 1e9;

int main()
{
	freopen("mkt.in", "r", stdin);
	freopen("mkt.out", "w", stdout);	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; i++) cin >> a[i];
		vector<vector<int>> dp(n + 1, vector<int>(2, INF));
		dp[0][0] = 0;
		for (int i = 0; i < n; i++)
		{
			if (dp[i][0] != INF)
			{
				dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + a[i]);
				if (i + 2 <= n)
				{
					dp[i + 2][1] = min(dp[i + 2][1], dp[i][0] + a[i] + a[i + 1]);
				}
			}
			if (dp[i][1] != INF)
			{
				dp[i + 1][0] = min(dp[i + 1][0], dp[i][1]);
				if (i + 2 <= n)
				{
					dp[i + 2][0] = min(dp[i + 2][0], dp[i][1]);
				}
			}
		}
		cout << min(dp[n][0], dp[n][1]) << '\n';
	}
	return 0;
}

B.k-Tree

核心思路

使用动态规划统计从根出发、路径权值和为 n 的路径数量，并区分是否已经使用过权值 ≥ d 的边。由于边权范围为 1..k，路径长度不限，本质上是完全背包计数问题，加一个状态记录是否满足“至少一条边 ≥ d”的条件。

具体步骤

定义状态
- dp[i][0]：路径权值和为 i，且当前路径中没有任何边的权值 ≥ d 的方案数。
- dp[i][1]：路径权值和为 i，且当前路径中至少有一条边的权值 ≥ d 的方案数。
初始化
- 根到自身的路径权值和为 0，且尚未使用任何边，因此 dp[0][0] = 1，dp[0][1] = 0。
状态转移
- 枚举当前路径和 i（0 ≤ i ≤ n）。
- 枚举下一条边的权值 w（1 ≤ w ≤ k），若 i + w ≤ n：
  - 如果 w ≥ d，则新路径必定满足条件，因此：
    - dp[i+w][1] += dp[i][0] + dp[i][1]（所有旧状态都变为已满足）。
  - 如果 w < d，则新路径的满足状态与旧状态相同：
    - dp[i+w][0] += dp[i][0]
    - dp[i+w][1] += dp[i][1]
取模
- 所有加法对 1e9+7 取模。
答案
- 最终输出 dp[n][1]，即路径权和为 n 且至少包含一条权值 ≥ d 的边的方案数。

题解

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

const int MOD = 1e9 + 7;

int main()
{
	freopen("ktree.in", "r", stdin);
	freopen("ktree.out", "w", stdout);
	int n, k, d;
	cin >> n >> k >> d;
	vector<vector<long long>> dp(n + 1, vector<long long>(2, 0));
	dp[0][0] = 1;
	for (int i = 0; i <= n; i++)
	{
		for (int w = 1; w <= k; w++)
		{
			if (i + w > n) break;
			if (w >= d)
			{
				dp[i + w][1] = (dp[i + w][1] + dp[i][0]) % MOD;
				dp[i + w][1] = (dp[i + w][1] + dp[i][1]) % MOD;
			}
			else
			{
				dp[i + w][0] = (dp[i + w][0] + dp[i][0]) % MOD;
				dp[i + w][1] = (dp[i + w][1] + dp[i][1]) % MOD;
			}
		}
	}
	cout << dp[n][1];
	return 0;
}

C.Parsa's Humongous Tree

核心思路

对于每个顶点，最优取值只会出现在其区间的两个端点（即 l_v 或 r_v）。因此可以用树形 DP，对每个节点分别记录取左端点或右端点时，以其为根的子树能获得的最大边权和。转移时考虑当前节点与每个子节点的四种组合，取绝对值贡献最大者累加。

具体步骤

读入数据：每个测试用例的顶点数 n，每个顶点的区间 [l_i, r_i]，以及树的边。
建立 DFS 顺序：从根节点 1 开始，用栈得到从叶子到根的遍历顺序（后序遍历），便于 DP 自底向上计算。
定义 DP 状态：
- dp0[v]：顶点 v 取 l_v 时，子树 v 内部所有边的最大贡献和。
- dp1[v]：顶点 v 取 r_v 时，子树 v 内部的最大贡献和。
转移：对每个顶点 v，遍历其子节点 u：
- 若 v 取 l_v，则与子节点 u 的贡献取 max(dp0[u] + |l_v - l_u|, dp1[u] + |l_v - r_u|)。
- 若 v 取 r_v，则贡献取 max(dp0[u] + |r_v - l_u|, dp1[u] + |r_v - r_u|)。
- 分别累加到 sum0 和 sum1。
赋值：dp0[v] = sum0，dp1[v] = sum1。
答案：根节点 1 的两种取值中的较大者，即 max(dp0[1], dp1[1])。

题解

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

int main()
{
	freopen("parsatree.in", "r", stdin);
	freopen("parsatree.out", "w", stdout);
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		vector<ll> l(n + 1), r(n + 1);
		for (int i = 1; i <= n; i++)
		{
			cin >> l[i] >> r[i];
		}
		vector<vector<int>> g(n + 1);
		for (int i = 0; i < n - 1; i++)
		{
			int u, v;
			cin >> u >> v;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		vector<int> fa(n + 1, 0), f;
		stack<int> st;
		st.push(1);
		fa[1] = -1;
		while (!st.empty())
		{
			int v = st.top();
			st.pop();
			f.push_back(v);
			for (int u : g[v])
			{
				if (u == fa[v]) continue;
				fa[u] = v;
				st.push(u);
			}
		}
		vector<ll> dp0(n + 1, 0), dp1(n + 1, 0);
		for (int idx = n - 1; idx >= 0; idx--)
		{
			int v = f[idx];
			ll sum0 = 0, sum1 = 0;
			for (int u : g[v])
			{
				if (fa[u] != v) continue;
				ll best0 = max(dp0[u] + abs(l[v] - l[u]), dp1[u] + abs(l[v] - r[u]));
				ll best1 = max(dp0[u] + abs(r[v] - l[u]), dp1[u] + abs(r[v] - r[u]));
				sum0 += best0;
				sum1 += best1;
			}
			dp0[v] = sum0;
			dp1[v] = sum1;
		}
		cout << max(dp0[1], dp1[1]) << '\n';
	}
	return 0;
}

D.Four Segments

核心思路

利用前缀和将表达式化简，然后固定中间分隔符 d1，分别取左侧和右侧的最优位置，通过预处理前缀/后缀最大值实现 O(n) 求解。

具体步骤

计算前缀和
定义 S[0]=0，S[i]=a[0]+...+a[i-1]。则任意区间和 sum(l,r)=S[r]-S[l]。
化简目标式
原式 res = sum(0,d0) - sum(d0,d1) + sum(d1,d2) - sum(d2,n) 代入前缀和得：
res = 2*(S[d0] - S[d1] + S[d2]) - S[n]。
因为 S[n] 为常数，最大化 res 等价于最大化 F = S[d0] - S[d1] + S[d2]。
固定中间点
枚举 d1（0 ≤ d1 ≤ n）。对于每个 d1，最优的 d0 应在 [0, d1] 内取 S 最大值，最优的 d2 应在 [d1, n] 内取 S 最大值。
预处理前缀最大值
- pref_val[i] = max(S[0..i])，并用 pref_idx[i] 记录对应下标。
- suf_val[i] = max(S[i..n])，并用 suf_idx[i] 记录对应下标。
枚举求最优
遍历 d1，计算当前值 cur = pref_val[d1] - S[d1] + suf_val[d1]，取最大时记录三组下标 (pref_idx[d1], d1, suf_idx[d1])。
输出结果
输出最优的三个下标。若有多个最优，输出任意一组。

题解

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

int main() {
	freopen("fs.in", "r", stdin);
	freopen("fs.out", "w", stdout);
	int n;
	cin >> n;
	vector<long long> a(n);
	for (int i = 0; i < n; i ++) cin >> a[i];
	vector<long long> S(n + 1, 0);
	for (int i = 0; i < n; i ++) S[i + 1] = S[i] + a[i];
	vector<long long> pre_val(n + 1);
	vector<int> pre_idx(n + 1);
	pre_val[0] = S[0];
	pre_idx[0] = 0;
	for (int i = 1; i <= n; i ++) 
	{
		if (S[i] > pre_val[i - 1])
		{
			pre_val[i] = S[i];
			pre_idx[i] = i;
		} 
		else 
		{
			pre_val[i] = pre_val[i - 1];
			pre_idx[i] = pre_idx[i - 1];
		}
	}
	vector<long long> suf_val(n + 1);
	vector<int> suf_idx(n + 1);
	suf_val[n] = S[n];
	suf_idx[n] = n;
	for (int i = n - 1; i >= 0; i --) 
	{
		if (S[i] > suf_val[i + 1]) 
		{
			suf_val[i] = S[i];
			suf_idx[i] = i;
		} 
		else 
		{
			suf_val[i] = suf_val[i + 1];
			suf_idx[i] = suf_idx[i + 1];
		}
	}
	long long best = LLONG_MIN;
	int best_d0 = 0, best_d1 = 0, best_d2 = 0;
	for (int d1 = 0; d1 <= n; d1 ++) 
	{
		long long cur = pre_val[d1] - S[d1] + suf_val[d1];
		if (cur > best) 
		{
			best = cur;
			best_d0 = pre_idx[d1];
			best_d1 = d1;
			best_d2 = suf_idx[d1];
		}
	}	
	cout << best_d0 << ' ' << best_d1 << ' ' << best_d2 << '\n';
	return 0;
}

E.Slime

核心思路

利用合并操作的特性：最终分数等于所有数的绝对值之和减去某些代价。当数组中既有正数又有负数时，可以通过合适的合并顺序使最终结果等于所有绝对值之和；当所有数同号时，必须牺牲绝对值最小的那个数，使其符号变为相反，因此答案是总和减去两倍的最小绝对值。

具体步骤

读入 n 和数组 a。
如果 n == 1，直接输出 a[0]。
计算：
- sum = Σ |a[i]|（所有数的绝对值之和）
- mn = min |a[i]|（最小的绝对值）
- 标记是否存在正数和负数。
判断：
- 若同时存在正数和负数，则答案为 sum。
- 若全为正或全为负（且 n > 1），则答案为 sum - 2 * mn。
输出答案。

题解

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

int main()
{
	freopen("slime.in", "r", stdin);
	freopen("slime.out", "w", stdout);
	int n;
	cin >> n;
	vector<ll> a(n);
	ll sum = 0, mn = LLONG_MAX;
	bool pn = false, nn = false;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		if (a[i] > 0) pn = true;
		if (a[i] < 0) nn = true;
		ll val = llabs(a[i]);
		sum += val;
		mn = min(mn, val);
	}
	if (n == 1)
	{
		cout << a[0];
		return 0;
	}
	if (pn && nn)
	{
		cout << sum;
	}
	else
	{
		cout << sum - 2 * mn;
	}
	return 0;
}

F.Recovering BST

核心思路

给定升序的互异数组，要求构造一棵二叉搜索树，使得每条边两端点的最大公约数 > 1。由于数组已排序，任意区间 [l, r] 对应二叉搜索树的一棵子树（值在区间内）。用区间 DP 判断每个子区间能否作为合法的子树，并记录它能否连接到左父节点或右父节点（即与区间外相邻节点的 gcd > 1）。最后检查是否存在一个根节点使得左右子树均合法。

具体步骤

预处理边权合法性
对任意两个节点 i < j，若 gcd(a[i], a[j]) > 1，则标记 good[i][j] = good[j][i] = true。
定义 DP 状态
- L[l][r]：区间 [l, r] 能够作为某个节点的左子树，即该区间的根可以与 l-1 号节点相连（l > 1 且 good[l-1][root] 为真）。
- R[l][r]：区间 [l, r] 能够作为某个节点的右子树，即根可以与 r+1 号节点相连（r < n 且 good[root][r+1] 为真）。
区间 DP 转移
按区间长度从小到大枚举所有区间 [l, r]：
- 枚举区间内可能的根 k（即子树的根节点）。
- 判断左子树 [l, k-1] 是否合法：若 k == l，则左子树为空，合法；否则需要 R[l][k-1] 为真（即左子树可以作为根 k 的左子树）。
- 判断右子树 [k+1, r] 是否合法：若 k == r，则右子树为空，合法；否则需要 L[k+1][r] 为真。
- 若左右子树均合法，则说明以 k 为根的区间 [l, r] 在内部结构上可行。此时：
  - 若 l > 1 且 good[l-1][k]，则 L[l][r] = true（该区间可作为 l-1 的左子树）。
  - 若 r < n 且 good[k][r+1]，则 R[l][r] = true（该区间可作为 r+1 的右子树）。
- 对于已经找到可行根的区间，可以提前终止当前区间的枚举（不影响最终结果），但代码中的提前退出条件较为保守，不会导致错误。
检查整体可行性
枚举根节点 root（1..n）：
- 左子树区间 [1, root-1] 必须合法（若为空则无需条件，否则需要 R[1][root-1] 为真）。
- 右子树区间 [root+1, n] 必须合法（若为空则无需条件，否则需要 L[root+1][n] 为真）。
- 若均满足，则输出 "Yes"。
若所有根均不满足，输出 "No"。

题解

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

const int N = 705;
int n;
long long a[N];
bool good[N][N], L[N][N], R[N][N];

int main()
{
	freopen("bst.in", "r", stdin);
	freopen("bst.out", "w", stdout);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	for(int i = 1; i <= n; i++)
		for(int j = i + 1; j <= n; j++)
			good[i][j] = good[j][i] = (__gcd(a[i], a[j]) > 1);
	
	for(int len = 1; len <= n; len ++)
		for(int l = 1; l + len - 1 <= n; l++)
		{
			int r = l + len - 1;
			for(int k = l; k <= r; k++)
			{
				bool leftok = (k == l || R[l][k - 1]);
				bool rightok = (k == r || L[k + 1][r]);
				if(!leftok || !rightok) continue;
				
				if(l > 1 && good[l - 1][k]) L[l][r] = true;
				if(r < n && good[r + 1][k]) R[l][r] = true;
				
				if((l == 1 || L[l][r]) && (r == n || R[l][r]))
					break;
				
			}
		}
	for(int root = 1; root <= n; root ++)
	{
		bool leftok = (root == 1 || R[1][root - 1]);
		bool rightok = (root == n || L[root + 1][n]);
		
		if(leftok && rightok)
		{
			cout << "Yes";
			return 0;
		}
		
	}
	cout << "No";
	return 0;
}

作者已关闭评论

A.Mortal Kombat Tower

核心思路

具体步骤

题解

B.k-Tree

核心思路

具体步骤

题解

C.Parsa's Humongous Tree

核心思路

具体步骤

题解

D.Four Segments

核心思路

具体步骤

题解

E.Slime

核心思路

具体步骤

题解

F.Recovering BST

核心思路

具体步骤

题解

评论

还没有账户？

登录