P2339 提交作业usaco
题目背景
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
输出格式：
输出格式
• 单个整数，表示贝西交完作业后走到车站的最短时间
输入输出样例
说明
走到坐标 8 处，第 9 分钟交一本作业，等到第 12 分钟时，交另一本作业。再走到坐标 4 处交作业，最后走到坐标 3 处，交最后一本作业，此地就是车站所在位置，共用时 22 分钟
/*
直接想dp不好设状态，那就看看有什么性质......
容易想到把教室排序，如果一段区间[l,r]
先选外侧的教室交作业一定比先选里面的再出来再去另一边更优
那么答案就可以从外往里递推而来
再就是这种也可以向左也可以向右的题目一般来说都是转化为区间dp
f[l][r][0/1]表示决策到[l,r]这段区间，区间外的都已满足，选则l/r交作业的最短时间
转移看从那个教室移动过来即可。
*/
#include<bits/stdc++.h> #define N 1007 using namespace std;
int n,m,ans,cnt;
int f[N][N][];
struct node{
int Time,pos;
bool operator < (const node &a) const{
return pos<a.pos;
} }a[N]; inline int read()
{
int x=,f=;char c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} int main()
{
int C,H,B;
C=read();H=read();B=read();
for(int i=;i<=C;i++)
a[i].pos=read(),a[i].Time=read();
sort(a+,a+C+);
memset(f,/,sizeof f);
f[][C][]=max(a[].Time,a[].pos);
f[][C][]=max(a[C].Time,a[C].pos); for(int L=C-;L>=;L--) for(int i=;i+L<=C;++i)
{
int j=i+L;
f[i][j][]=min(max(f[i-][j][]+a[i].pos-a[i-].pos,a[i].Time),
max(f[i][j+][]+ a[j+].pos-a[i].pos,a[i].Time));
f[i][j][]=min(max(f[i-][j][]+a[j].pos - a[i-].pos,a[j].Time),
max(f[i][j+][]+ a[j+].pos-a[j].pos,a[j].Time));
}
ans=0x3f3f3f3f;
for (int i=;i<=C;i++)
ans=min(ans,f[i][i][]+abs(a[i].pos-B));
printf("%d\n",ans);
return ;
}