自动搬运

查看原文

来自洛谷，原作者为

	dzz1537568241 愿你的所有努力，都不负韶华

搬运于2025-08-24 21:36:32，当前版本为作者最后更新于2019-10-02 17:23:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实就是一道很裸的区间dp + 贪心，我们分成两部分考虑

一：贪心

最佳策略应该是由下面两种状态转移过来的

1. 向左或向右移动到 下一个教室 交作业

2. 从一个端点移动到另一个端点

如果先去中间某个教室，之后必然还要走到i教室和j教室，那么不如先去i教室或者j教室，之后去另一端的教室时必然会经过中间的教室交作业。

二：区间dp

先把教室按照x轴上的坐标排序

struct node{
	int x, t;
	bool operator < (const node &b)const{
		return x < b.x;
	}
}a[maxc];
int main(){
	cin>>C>>H>>B;
	for(int i = 1; i <= C; i++){
		cin>>a[i].x>>a[i].t;
	}
	sort(a + 1, a + 1 + C);
}

所有数轴上的dp题目基本都是f[maxn][maxn][2]这样的数组，

• 用f[ i ][ j ][ 0 ]来表示 当前人 在区间[ i , j ] 的左端点

• 用f[ i ][ j ][ 1 ]来表示 当前人 在区间[ i , j ] 的右端点

在这道题目里要稍微懂得灵活变通一点，

• 用f[ i ][ j ][ 0 ]来表示 当前人 在区间[ i , j ] 的左端点, 且区间[i + 1, j]的教室没有交作业

• 用f[ i ][ j ][ 1 ]来表示 当前人 在区间[ i , j ] 的右端点，且区间[i, j - 1]的教室还没有交作业

这样就能写出状态转移方程式：

f[i][j][0] = min(f[i][j][0], max(f[i - 1][j][0] + a[i].x - a[i - 1].x, a[i].t) );
f[i][j][0] = min(f[i][j][0], max(f[i][j + 1][1] + a[j + 1].x - a[i].x, a[i].t) );
f[i][j][1] = min(f[i][j][1], max(f[i][j + 1][1] + a[j + 1].x - a[j].x, a[j].t) );
f[i][j][1] = min(f[i][j][1], max(f[i - 1][j][0] + a[j].x - a[i - 1].x, a[j].t) );

每次枚举的是最后停留的点，f[i][i]就是最后停留到i点时的最小耗时，注意这里j需要倒序枚举

	for(int i = 1; i <= C; i++){
		for(int j = C; j >= i; j--){
			f[i][j][0] = min(f[i][j][0], max(f[i - 1][j][0] + a[i].x - a[i - 1].x, a[i].t) );
			f[i][j][0] = min(f[i][j][0], max(f[i][j + 1][1] + a[j + 1].x - a[i].x, a[i].t) );
			f[i][j][1] = min(f[i][j][1], max(f[i][j + 1][1] + a[j + 1].x - a[j].x, a[j].t) );
			f[i][j][1] = min(f[i][j][1], max(f[i - 1][j][0] + a[j].x - a[i - 1].x, a[j].t) );
		}
	}

最后给出全部代码：

#include <iostream>
#include <cstdio>
#define INF 0x3f3f3f
#include <cstring>
#include <algorithm>
using namespace std;
int C,H,B;
const int maxc = 1050, maxh = 1050; 
int f[maxc][maxc][2];
struct node{
	int x, t;
	bool operator < (const node &b)const{
		return x < b.x;
	}
}a[maxc];
int main(){
	cin>>C>>H>>B;
	for(int i = 1; i <= C; i++){
		cin>>a[i].x>>a[i].t;
	}
	sort(a + 1, a + 1 + C);
	memset(f, INF,sizeof(f));
	f[1][C][0] = max(a[1].x,a[1].t);
	f[1][C][1] = max(a[C].x,a[C].t);
	for(int i = 1; i <= C; i++){
		for(int j = C; j >= i; j--){
			f[i][j][0] = min(f[i][j][0], max(f[i - 1][j][0] + a[i].x - a[i - 1].x, a[i].t) );
			f[i][j][0] = min(f[i][j][0], max(f[i][j + 1][1] + a[j + 1].x - a[i].x, a[i].t) );
			f[i][j][1] = min(f[i][j][1], max(f[i][j + 1][1] + a[j + 1].x - a[j].x, a[j].t) );
			f[i][j][1] = min(f[i][j][1], max(f[i - 1][j][0] + a[j].x - a[i - 1].x, a[j].t) );
		}
	}
	int ans = INF;
	for(int i=1;i<=C;i++)
    {
        ans = min(ans,min(f[i][i][0]+abs(a[i].x - B), f[i][i][1] + abs(a[i].x-B)));
    }
    cout<<ans;
}