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][2]; struct node{ int Time,pos; bool operator < (const node &a) const{ return pos<a.pos; } }a[N]; inline int read() { int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int main() { int C,H,B; C=read();H=read();B=read(); for(int i=1;i<=C;i++) a[i].pos=read(),a[i].Time=read(); sort(a+1,a+C+1); memset(f,127/3,sizeof f); f[1][C][0]=max(a[1].Time,a[1].pos); f[1][C][1]=max(a[C].Time,a[C].pos); for(int L=C-2;L>=0;L--) for(int i=1;i+L<=C;++i) { int j=i+L; f[i][j][0]=min(max(f[i-1][j][0]+a[i].pos-a[i-1].pos,a[i].Time), max(f[i][j+1][1]+ a[j+1].pos-a[i].pos,a[i].Time)); f[i][j][1]=min(max(f[i-1][j][0]+a[j].pos - a[i-1].pos,a[j].Time), max(f[i][j+1][1]+ a[j+1].pos-a[j].pos,a[j].Time)); } ans=0x3f3f3f3f; for (int i=1;i<=C;i++) ans=min(ans,f[i][i][0]+abs(a[i].pos-B)); printf("%d ",ans); return 0; }