【bzoj3379】[Usaco2004 Open]Turning in Homework 交作业 区间dp

时间:2022-01-09 08:35:03

题目描述

数轴上有C个点,每个点有一个坐标和一个访问时间,必须在这个时间后到达这个点才算访问完成。可以在某个位置停留。每在数轴上走一个单位长度消耗一个单位的时间,问:访问所有点并最终到B花费的最小时间。

输入

第1行输入三个整数C,H,B,B是出口的位置.之后C行每行输入两个整数,分别表示一个老师所在的教室和他的下课时间.

输出

贝茜最早能够到达出口的时间.

样例输入

4 10 3
8 9
4 21
3 16
8 12

样例输出

22


题解

区间dp

考试题。。。考挂了。。。

(以下内容复制自题解)

考虑 dp[i][j][0/1]表示已经处理了从左数的 i 个和从右数的 j 个的案件,当前在 i 还是在 j
dp[i][j][0]可以由 dp[i-1][j][0],dp[i][j+1][1]+dis 来转移
dp[i][j][1]同理。

(以上内容复制自题解)

个人想法:

首先一定是先处理区间端点。一个大概思路是:对于非必选的点能不选就不选,而区间端点必选,其余点不必选,因此只需要考虑区间端点。

(或者一个更好的思考方法是:考虑把这个过程反过来,变为从$B$开始走,每个点必须在$ANS-T_i$时间内到达,最终要求到达0位置。显然经过的点一定不会傻到不选,因此反过程先选中间再选端点,正过程就是先选端点再选中间。
PS:$ANS$满足单调性,因此CQzhangyu就这样切了此题。。)

然后设$f[i][j][0/1]$表示左端点为$i$,右端点为$j$,当前处理完$i/j$的最小时间。直接转移即可。注意一下这是一个半开半闭区间的状态,因此初始状态需要计算,最终答案直接用$f[i][i][0/1]$统计。

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

代码简单的不行= =

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1010
using namespace std;
struct data
{
int p , t;
bool operator<(const data &a)const {return p < a.p;}
}a[N];
int f[N][N][2];
int main()
{
int n , m , i , j , k , ans = 1 << 30;
scanf("%d%*d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ ) scanf("%d%d" , &a[i].p , &a[i].t);
sort(a + 1 , a + n + 1);
memset(f , 0x3f , sizeof(f));
f[1][n][0] = max(a[1].p , a[1].t) , f[1][n][1] = max(a[n].p , a[n].t);
for(k = n - 1 ; k ; k -- )
{
for(i = 1 ; i <= n - k + 1 ; i ++ )
{
j = i + k - 1;
if(i > 1) f[i][j][0] = min(f[i][j][0] , f[i - 1][j][0] + a[i].p - a[i - 1].p) , f[i][j][1] = min(f[i][j][1] , f[i - 1][j][0] + a[j].p - a[i - 1].p);
if(j < n) f[i][j][0] = min(f[i][j][0] , f[i][j + 1][1] + a[j + 1].p - a[i].p) , f[i][j][1] = min(f[i][j][1] , f[i][j + 1][1] + a[j + 1].p - a[j].p);
f[i][j][0] = max(f[i][j][0] , a[i].t) , f[i][j][1] = max(f[i][j][1] , a[j].t);
}
}
for(i = 1 ; i <= n ; i ++ ) ans = min(ans , min(f[i][i][0] , f[i][i][1]) + abs(a[i].p - m));
printf("%d\n" , ans);
return 0;
}