POJ 1991 Turning in Homework(区间DP)

时间:2022-03-24 13:17:40

题目链接 Turning in Homework

考虑区间DP

$f[i][j][0]$为只考虑区间$[i, j]$且最后在$a[i]$位置交作业的答案。

$f[i][j][1]$为只考虑区间$[i, j]$且最后在$a[j]$位置交作业的答案。

首先对$a[i]$升序排序(位置第一关键字,时间第二关键字)

然后就是区间DP了

$f[i][j]$可以从$f[i][j + 1]$, $f[i - 1][j]$推过来。

$f[i][j][0] = min(f[i][j][0], max(f[i][j + 1][1] + a[j + 1].fi - a[i].fi, a[i].se))$

$f[i][j][0] = min(f[i][j][0], max(f[i - 1][j][0] + a[i].fi - a[i - 1].fi, a[i].se))$

$f[i][j][1] = min(f[i][j][1], max(f[i - 1][j][0] + a[j].fi - a[i - 1].fi, a[j].se));$

$f[i][j][1] = min(f[i][j][1], max(f[i][j + 1][1] + a[j + 1].fi - a[j].fi, a[j].se));$

其中$fi$代表位置,$se$代表时间。

最后的答案为$min{min(f[i][i][0], f[i][i][1]) + abs(a[i].fi - B)}$

$B$位规定的终点。

时间复杂度$O(n^{2})$

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define MP make_pair
#define fi first
#define se second typedef long long LL; const int N = 1010;
int n, m, ed, ans;
pair <int, int> a[N];
int f[N][N][2]; int main(){ scanf("%d%d%d", &n, &m, &ed);
rep(i, 1, n) scanf("%d%d", &a[i].fi, &a[i].se);
sort(a + 1, a + n + 1); f[1][n][0] = max(a[1].fi, a[1].se);
f[1][n][1] = max(a[n].fi, a[n].se); dec(d, n - 1, 1){
rep(i, 1, n - d + 1){
int j = i + d - 1;
f[i][j][0] = 1 << 30;
if (j < n) f[i][j][0] = min(f[i][j][0], max(f[i][j + 1][1] + a[j + 1].fi - a[i].fi, a[i].se));
if (i > 1) f[i][j][0] = min(f[i][j][0], max(f[i - 1][j][0] + a[i].fi - a[i - 1].fi, a[i].se)); f[i][j][1] = 1 << 30;
if (i > 1) f[i][j][1] = min(f[i][j][1], max(f[i - 1][j][0] + a[j].fi - a[i - 1].fi, a[j].se));
if (j < n) f[i][j][1] = min(f[i][j][1], max(f[i][j + 1][1] + a[j + 1].fi - a[j].fi, a[j].se));
}
} ans = 1 << 30;
rep(i, 1, n) ans = min(ans, min(f[i][i][0], f[i][i][1]) + abs(a[i].fi - ed));
printf("%d\n", ans);
return 0;
}