P3842 [TJOI2007] 线段

发布于:2024-07-11 ⋅ 阅读:(24) ⋅ 点赞:(0)

这道题半年前刚学动态规划的时候就有尝试过,但没有成功解出来,就一直放到现在。军训的某一天,又翻到这题,重新再来!

题目描述

在一个 n × n n \times n n×n 的平面上,在每一行中有一条线段,第 i i i 行的线段的左端点是 ( i , L i ) (i, L_{i}) (i,Li),右端点是 ( i , R i ) (i, R_{i}) (i,Ri)

你从 ( 1 , 1 ) (1,1) (1,1) 点出发,要求沿途走过所有的线段,最终到达 ( n , n ) (n,n) (n,n) 点,且所走的路程长度要尽量短。

更具体一些说,你在任何时候只能选择向下走一步(行数增加 1 1 1)、向左走一步(列数减少 1 1 1)或是向右走一步(列数增加 1 1 1)。当然,由于你不能向上行走,因此在从任何一行向下走到另一行的时候,你必须保证已经走完本行的那条线段。

输入格式

第一行有一个整数 n n n

以下 n n n 行,在第 i i i 行(总第 ( i + 1 ) (i+1) (i+1) 行)的两个整数表示 L i L_i Li R i R_i Ri

输出格式

仅包含一个整数,你选择的最短路程的长度。

样例 #1

样例输入 #1

6
2 6
3 4
1 3
1 2
3 6
4 5

样例输出 #1

24

提示

我们选择的路线是

 (1, 1) (1, 6)
 (2, 6) (2, 3)
 (3, 3) (3, 1)
 (4, 1) (4, 2)
 (5, 2) (5, 6)
 (6, 6) (6, 4) (6, 6)

不难计算得到,路程的总长度是 24 24 24

对于 100 % 100\% 100% 的数据中, n ≤ 2 × 1 0 4 n \le 2 \times 10^4 n2×104 1 ≤ L i ≤ R i ≤ n 1 \le L_i \le R_i \le n 1LiRin

开始思路

第一行特判,接下来拎出相邻两行看,上一行端点a b,下一行端点c ddp[ ]的意思是“上一行以该端点为结尾的情况下最短路径和”,所以需要计算下面一行c d端点分别从a b下来的最小路径,取min,到最后一行取两个端点中的最小值即可。

核心dp代码

dp[L[i]] = min(dp[L[i-1]] + R[i] - L[i] + abs(L[i-1] - R[i]), dp[R[i-1] + R[i] - L[i] + abs(R[i-1] - R[i]))

问题代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 2 * 1e4 + 5;
int n, L[N], R[N], dp[N];

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) cin >> L[i] >> R[i];
	dp[L[0]] = R[0] - 1 + (R[0] - L[0]);
	dp[R[0]] = R[0] - 1;
	
	for (int i = 1; i < n; i++) {
		int length = R[i] - L[i];
		
		dp[L[i]] = min(dp[L[i - 1]] + abs(L[i - 1] - R[i]), dp[R[i - 1]] + abs(R[i - 1] - R[i])) + length + 1;
        dp[R[i]] = min(dp[L[i - 1]] + abs(L[i - 1] - L[i]), dp[R[i - 1]] + abs(R[i - 1] - L[i])) + length + 1;
	}
	int ans = min(dp[L[n - 1]], dp[R[n - 1]]);
	cout << ans;
	
	return 0;
}

提交后爆0

反思

  1. 每一行的左右两个端点可能会互相影响,题干中 1 ≤ L i ≤ R i ≤ n 1 \le L_i \le R_i \le n 1LiRin L i 和 R i L_i和 R_i LiRi可以相等,即为一点。所以需要用临时变量暂时储存
  2. 忽略了题干中的最终到达 ( n , n ) (n,n) (n,n)

AC代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 2 * 1e4 + 5;
int n, L[N], R[N], dp[N];

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) cin >> L[i] >> R[i];
	dp[L[0]] = R[0] - 1 + (R[0] - L[0]);
	dp[R[0]] = R[0] - 1;
	
	for (int i = 1; i < n; i++) {
		int length = R[i] - L[i];
		
		int tmp_L = min(dp[L[i - 1]] + abs(L[i - 1] - R[i]), dp[R[i - 1]] + abs(R[i - 1] - R[i])) + length + 1;
        int tmp_R = min(dp[L[i - 1]] + abs(L[i - 1] - L[i]), dp[R[i - 1]] + abs(R[i - 1] - L[i])) + length + 1;

        dp[L[i]] = tmp_L;
        dp[R[i]] = tmp_R;
	}
	int ans = min(dp[L[n - 1]] + n - L[n - 1], dp[R[n - 1]] + n - R[n - 1]);
	cout << ans;
	
	return 0;
}