题解 P2339 【提交作业usaco】

dzz1537568241 · 2019-10-02 17:23:35 · 题解

其实就是一道很裸的区间dp + 贪心，我们分成两部分考虑

一：贪心

最佳策略应该是由下面两种状态转移过来的

1. 向左或向右移动到 下一个教室 交作业

1. 从一个端点移动到另一个端点

如果先去中间某个教室，之后必然还要走到i教室和j教室，那么不如先去i教室或者j教室，之后去另一端的教室时必然会经过中间的教室交作业。

二：区间dp

先把教室按照x轴上的坐标排序

struct node{
    int x, t;
    bool operator < (const node &b)const{
        return x < b.x;
    }
}a[maxc];
int main(){
    cin>>C>>H>>B;
    for(int i = 1; i <= C; i++){
        cin>>a[i].x>>a[i].t;
    }
    sort(a + 1, a + 1 + C);
}

所有数轴上的dp题目基本都是f[maxn][maxn][2]这样的数组，

• 用f[ i ][ j ][ 0 ]来表示 当前人 在区间[ i , j ] 的左端点

• 用f[ i ][ j ][ 1 ]来表示 当前人 在区间[ i , j ] 的右端点

在这道题目里要稍微懂得灵活变通一点，

• 用f[ i ][ j ][ 0 ]来表示 当前人 在区间[ i , j ] 的左端点, 且区间[i + 1, j]的教室没有交作业

• 用f[ i ][ j ][ 1 ]来表示 当前人 在区间[ i , j ] 的右端点，且区间[i, j - 1]的教室还没有交作业

这样就能写出状态转移方程式：

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][j + 1][1] + a[j + 1].x - a[j].x, a[j].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][i]就是最后停留到i点时的最小耗时，注意这里j需要倒序枚举

    for(int i = 1; i <= C; i++){
        for(int j = C; j >= i; 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][j + 1][1] + a[j + 1].x - a[j].x, a[j].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) );
        }
    }

最后给出全部代码：

#include <iostream>
#include <cstdio>
#define INF 0x3f3f3f
#include <cstring>
#include <algorithm>
using namespace std;
int C,H,B;
const int maxc = 1050, maxh = 1050; 
int f[maxc][maxc][2];
struct node{
    int x, t;
    bool operator < (const node &b)const{
        return x < b.x;
    }
}a[maxc];
int main(){
    cin>>C>>H>>B;
    for(int i = 1; i <= C; i++){
        cin>>a[i].x>>a[i].t;
    }
    sort(a + 1, a + 1 + C);
    memset(f, INF,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(int i = 1; i <= C; i++){
        for(int j = C; j >= i; 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][j + 1][1] + a[j + 1].x - a[j].x, a[j].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) );
        }
    }
    int ans = INF;
    for(int i=1;i<=C;i++)
    {
        ans = min(ans,min(f[i][i][0]+abs(a[i].x - B), f[i][i][1] + abs(a[i].x-B)));
    }
    cout<<ans;
}