POJ 1991 Turning in Homework ★(区间DP)

题目大意：在一条长为 H (0..1000) 的走廊上有 C (0..1000) 个教室，Bessie 需要去每个教室都交一次作业。每个作业有个最早可以提交的时间。Bessie 在交完所有作业后需要去走廊的 B (0<=B<=H) 位置离开。给出 C 个教室的位置，和相应作业最早可以提交的时间 (0..10,000)，求出 Bessie 最早的离开时间。（Bessie 一开始在走廊的一端，位置 0。Bessie 每秒走 1 个单位长）一开始没什么头绪，看了题解知道一个结论后就明显了：如果某段区间[x,y]没被访问并且此时站在x or y处，那么最优的方案一定是先走两个端点（自己推一下~）那么就是一个处理区间两端点的区间DP了设l[i][j]表示i到j还没交，站在i处的最优值；r[i][j]表示i到j还没交，站在j处的最优值。 l[i][j] = max(l[i-1][j], time[i-1])+1 //站在左端点，去左端点 r[i][j] = max(r[i][j+1], time[j+1])+1 //站在右端点，去右端点 l[i][j] = min(l[i][j], r[i][j] + j - i) //站在左端点，去右端点 r[i][j] = min(r[i][j], l[i][j] + j- i) //站在右端点，去左端点代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MID(x,y) ((x+y)>>1)
using namespace std;
typedef long long LL;
const int N = 1010;
const int sup = 100000000;
int l[N][N], r[N][N];
int time[10*N];
int C, H, B;
int main(){
    scanf("%d %d %d", &C, &H, &B);
    memset(time, 0, sizeof(time));
    H = B;
    for (int i = 0; i < C; i ++){
        int tmp_position, tmp_time;
        scanf("%d %d", &tmp_position, &tmp_time);
        time[tmp_position] = max(time[tmp_position], tmp_time);
        H = max(H, tmp_position);
    }
    for (int i = 0; i <= H; i ++)
        for (int j = 0; j <= H; j ++)
            l[i][j] = sup, r[i][j] = sup;
    l[0][H] = 0;
    for (int k = H; k >= 0; k --){
        for (int i = 0; i <= H; i ++){
            if (i + k > H)
                break;
            int j = i + k;
            if (i > 0)  l[i][j] = max(l[i-1][j], time[i-1]) + 1;
            if (j < H)  r[i][j] = max(r[i][j+1], time[j+1]) + 1;
            l[i][j] = min(l[i][j], r[i][j] + k);
            r[i][j] = min(r[i][j], l[i][j] + k);
        }
    }
    printf("%d\n", max(min(l[B][B], r[B][B]), time[B]));
	return 0;
}

举杯独醉，饮罢飞雪，茫然又一年岁。 ------AbandonZHANG