【luogu P2339提交作业】题解

提交作业

题目背景

usaco

题目描述

贝西在哞哞大学选修了 C 门课，她要把所有作业分别交给每门课的老师，然后去车站和同学们一起回家。

每个老师在各自的办公室里，办公室要等他们下课后才开，第 i 门课的办公室将在 Ti 分钟后开放。

所有的办公室都在一条笔直的走廊上，这条走廊长 H 个单位，一开始贝西在走廊的尽头一侧，位于坐标为 0 的地方。

第 i 门课的办公室坐标位于坐标为 Xi 的地方，车站的坐标为 B。

贝西可在走廊上自由行走，每分钟可以向右或者向左移动一个单位，也可以选择停着不移动。

如果走到一间已经开门的办公室，贝西就可以把相应的作业交掉了，走进办公室交作业是不计时间的。

请帮助贝西计算一下，从她开始交作业开始，直到到交完所有作业，再走到车站，最短需要多少时间时间。

输入格式

• 第一行：三个整数 C， H 和 B， 1 ≤ C ≤ 1000 , 1 ≤ H ≤ 1000 , 0 ≤ B ≤ H

• 第二行到 C + 1 行：第 i + 1 行有两个整数 Xi 和 Ti， 0 ≤ Xi ≤ H , 0 ≤ Ti ≤ 10000

输出格式

• 单个整数，表示贝西交完作业后走到车站的最短时间

输入输出样例

输入 #1

输出 #1

说明/提示

走到坐标 8 处，第 9 分钟交一本作业，等到第 12 分钟时，交另一本作业。再走到坐标 4 处交作业，最后走到坐标 3 处，交最后一本作业，此地就是车站所在位置，共用时 22 分钟

首先将办公室按照 x 进行排序。

然后对我们考虑先交左右端点的作业，因为如果左右端点还未交，最终还是要走到端点去交作业的。

所以可以直接考虑在先交左右两个端点中的一个的作业，然后缩小区间，再按上述策略交作业。

这样我们最后枚举最后一个交作业的教室，利用之前dp出来的优解，更新答案即可。

对于dp方程，可以这样构造。

设f[i][j][0]表示区间[i , j] 中，只有 i 交了作业(左端点交了)。

　f[i][j][1]表示区间[i , j] 中，只有 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-1][j][0]+a[j].x-a[i-1].x,a[j].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));

a[i].x 为 i 号办公室的坐标，a[i].t 为 i 号办公室开门的时间(其他应该已经挺清晰的了)。

这道题个人认为比较难以理解的是为什么要先交左右两个端点的作业，

先交完两端的作业，再去交中间的作业，与交完中间的作业再去交两端的作业相比，只是为了避免考虑端点和中间点来回移动产生的不影响最优解的耗时。

理解了这个，我觉的剩下的dp就比较直接了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
#define abs(x) (x>0?x:(-(x)))
using namespace std;
const int N=1100;
int c,h,b;
int f[N][N][3];
struct node{
    int x,t;
    bool operator < (const node &temp) const{
        return x<temp.x;
    }
}a[N];
int main()
{
    int i,j;
    scanf("%d%d%d",&c,&h,&b);
    for(i=1;i<=c;i++) scanf("%d%d",&a[i].x,&a[i].t);
    sort(a+1,a+c+1);
    memset(f,0x7f,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(i=1;i<=c;i++)
        for(j=c;j>=i;j--){//dp核心
            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-1][j][0]+a[j].x-a[i-1].x,a[j].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));
        }
    int ans=1e9;
    for(i=1;i<=c;i++)
        ans=min(ans,min(f[i][i][0],f[i][i][1])+abs(a[i].x-b));//最后不要忘记去车站。
    printf("%d",ans);
}

【luogu P2339提交作业】 题解