本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15570096.html

题目链接

先按作业的提交地点排序。

设 dp(l,r,0/1)dp(l, r, 0/1) 为还剩 [l,r][l, r] 的作业没交，且下一步交 l(0),r(1)l(0), r(1) 的最小步数。

显然：

dp(l,r,0)=min⁡(max⁡(dp(l−1,r,0)+∣al−1−al∣, tl), max⁡(dp(l,r+1,1)+∣ar+1−al∣, tl))dp(l, r, 0)=\min(\max(dp(l-1, r, 0)+|a_{l-1}-a_l|, \,t_l),\, \max(dp(l, r+1, 1)+|a_{r+1}-a_l|,\, t_l))

dp(l,r,1)=min⁡(max⁡(dp(l−1,r,0)+∣al−1−ar∣, tr), max⁡(dp(l,r+1,1)+∣ar+1−ar∣, tr))dp(l, r, 1)=\min(\max(dp(l-1, r, 0)+|a_{l-1}-a_r|,\, t_r),\, \max(dp(l, r+1, 1)+|a_{r+1}-a_r|,\, t_r))

要从大区间向小区间推。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// Problem: P2339 [USACO04OPEN]Turning in Homework G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2339
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
#define N 1010
struct node
{
	int x, t; 
}d[N]; 
int n, m, i, j, k; 
int c, h, b; 
int dp[N][N][2]; 
int a[N], t[N]; 
int l, r, ans; 

bool cmp(node x, node y)
{
	return x.x<y.x; 
}

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
	memset(dp, 0x3f, sizeof(dp)); 
	c=read(); h=read(); b=read(); 
	for(i=1; i<=c; ++i) d[i].x=read(), d[i].t=read(); 
	sort(d+1, d+c+1, cmp); 
	for(i=1; i<=c; ++i) a[i]=d[i].x, t[i]=d[i].t; 
	// for(i=1; i<=c; ++i) printf("%lld %lld\n", a[i], t[i]); 
	dp[1][c][0]=max(a[1], t[1]); 
	dp[1][c][1]=max(a[c], t[c]); 
	// printf("dp[1][%lld][0]=%lld\n", c, dp[1][c][0]); 
	// printf("dp[1][%lld][1]=%lld\n", c, dp[1][c][1]); 
	for(k=c-1; k>=1; --k)
		for(l=1, r=l+k-1; r<=c; ++l, ++r)
		{
			dp[l][r][0]=min(max(dp[l-1][r][0]+abs(a[l-1]-a[l]), t[l]), 
							max(dp[l][r+1][1]+abs(a[r+1]-a[l]), t[l])); 
			dp[l][r][1]=min(max(dp[l-1][r][0]+abs(a[l-1]-a[r]), t[r]),
							max(dp[l][r+1][1]+abs(a[r+1]-a[r]), t[r])); 
			// printf("dp[%lld][%lld][0]=%lld\n", l, r, dp[l][r][0]); 
			// printf("dp[%lld][%lld][1]=%lld\n", l, r, dp[l][r][1]); 
		}
	ans=0x3f3f3f3f3f3f3f3f; 
	for(i=1; i<=c; ++i) ans=min(ans, min(dp[i][i][0], dp[i][i][1])+abs(a[i]-b)); 
	printf("%lld", ans); 
	return 0; 
}