2014NOIP提高组D1T3 飞扬的小鸟

依然wtm · 2018-11-01 23:58:50 · 题解

洛谷P1941 原题地址

这是一道DP题，也是一道终极细节题。朴素的DP方程还是比较好想的。如果用f[i][j]表示到第i列高度为j时的最小点击数的话，DP方程也就是

其中lift[i]是在第i列点击后上升的高度，down[i]是第i列下降的高度，k是在前一列点击的次数。要注意的就是高度为m时需要特判一下。

处理完了所有f[i][j]后，只需要从后往前扫一遍，找到能通到的一列，如果为第n列就输出1和最小点击数，否则输出0和柱子数。理论上这个算法时间复杂度为O(n^3)，应该能过70\%的数据。于是按照这个思路，我有了第一版的代码。

DP部分代码如下：

int nump = 1;
    for (int i = 1; i <= n; i++) {
        int lower = 0, upper = m;
        if (pipe[nump].pos == i) {
            upper = pipe[nump].up - 1;
            lower = pipe[nump++].bottom + 1;
        }
        for (int j = lower; j <= upper; j++) {
            for (int k = 1; j - k * lift[i - 1] >= 0; k++) { // 上升到（i，j）
                if (j == m) { // 特判m
                    for (int q = j - k * lift[i - 1]; q <= m ; q++)
                        f[i][j] = min(f[i][j], f[i - 1][q] + k);
                } else {
                    f[i][j] = min(f[i][j], f[i - 1][j - k * lift[i - 1]] + k);
                }
            }
            if (j + down[i - 1] <= m) f[i][j] = min(f[i][j], f[i - 1][j + down[i - 1]]); // 下降到（i，j）
        }
    }

但很不幸，这个代码并没有那到预期的70分，而是只有50。仔细读题后发现i = 0的时候是直接死掉的……在第二版代码中去掉j = 0的情况后，分果然变多了，变成了70分……虽然达到预期分数了，但发现有一个点并不是TLE，而是蛙WA了。于是乎下了数据，把所有f[i][j]打出来仔细研究（这是一种好方法）后发现，这句话

for (int k = 1; j - k * lift[i - 1] >= 0; k++)

中，j - k * lift[i - 1] >= 0的条件当j = m时有可能是错的，因为如果 m \% lift[i - 1] != 0，那么1到m \% lift[i - 1]的高度就枚举不到。举个例子，若m = 5，lift[i - 1] = 3，那么如果满足以上循环的条件的话，1和2这两个高度就枚举不到，而事实上当前状态完全有可能由这两个状态拓展而来。

发现了错误并进行改正后，第三版代码横空出世：

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

struct Pipe {
    int pos, up, bottom; // 柱子的位置，顶的高度和底的高度
} pipe[10010];

const int MAXN = (1 << 30);
int n, m, k, lift[10010], down[10010], f[10010][1010];

bool cmp(Pipe a, Pipe b) {
    return a.pos < b.pos;
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i <= n - 1; i++)
        scanf("%d%d", &lift[i], &down[i]);
    for (int i = 1; i <= k; i++)
        scanf("%d%d%d", &pipe[i].pos, &pipe[i].bottom, &pipe[i].up);
    sort(pipe + 1, pipe + k + 1, cmp); // 把柱子按列位置排序
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++)
            f[i][j] = MAXN;
    } // MAXN意味着到达不了（i，j）
    for (int i = 1; i <= m; i++) f[0][i] = 0; // 从第0列任意位置出发
    int nump = 1; // 下一个是第几个柱子
    for (int i = 1; i <= n; i++) {
        int lower = 1, upper = m;
        if (pipe[nump].pos == i) { // 如果这列有柱子
            upper = pipe[nump].up - 1;
            lower = pipe[nump++].bottom + 1;
        }
        for (int j = lower; j <= upper; j++) {
            if (j == m) { // 上升
                for (int k = 1; k <= m; k++) {
                    f[i][j] = min(f[i][j], f[i - 1][k] + ((m - k) / lift[i - 1]) + (((m - k) % lift[i - 1] || k == m) ? 1 : 0)); // 特判m
                }
            } else {
                for (int k = 1; j - k * lift[i - 1] >= 0; k++) {
                    f[i][j] = min(f[i][j], f[i - 1][j - k * lift[i - 1]] + k);
                } 
            }
            if (j + down[i - 1] <= m) f[i][j] = min(f[i][j], f[i - 1][j + down[i - 1]]); // 下降
        }
    int minn = MAXN;
    bool flag = false;
    for (int i = n; i >= 1; i--) { // 从后往前扫
        for (int j = 1; j <= m; j++) {
            if (f[i][j] != MAXN) {
                flag = true;
                minn = min(minn, f[i][j]); // 找到这一列的最小点击数
            }
        }
        if (flag) { // 输出
            if (i == n) {
                printf("1\n%d", minn);
                return 0;
            }
            else {
                for (int j = k; j >= 1; j--) {
                    if (i >= pipe[j].pos) {
                        printf("0\n%d", j);
                        return 0;
                    }
                }
            }
        }
    }
    printf("0\n0"); // 一个柱子也没过
    return 0;
}

这段代码已经超过了预期，用朴素算法拿到了80分的高分。那最后的20分怎么拿呢？观察代码，很明显更新上升的时候是有很多重复更新的。 我们先不考虑下降的情况，可以想到，在更新f[i][j]的时候，f[i][j - lift[i - 1]]已经更新得到了到(i, j - lift[i - 1])处的最小点击数，那么f[i][j]有两种更新的可能：一是从i - 1列上升一次到j，二是先从i - 1列上升k次到j - lift[i - 1]，再上升一次到j。而从i - 1列上升k次到j - lift[i - 1]的最优解已经存到了f[i][j - lift[i - 1]]里，所以我们有了一个新的上升时的DP方程：

特别要注意的是，用朴素DP的时候是可以不更新被柱子挡住的部分的，但是这个DP中需要更新下面的柱子挡住的部分（第四代代码被这个又卡了好久），因为这会影响到上面的计算，只要计算完再把柱子的部分赋回最大值就可以了。

更新完上升的情况后，正常再做一遍下降的更新就可以了。注意更新上升下降的顺序不能颠倒，因为根据我们的更新方法，颠倒顺序后可能出现先下降再上升的情况，而这是不符合题意的。

AC代码（第五代代码）如下：

#include<bits/stdc++.h>
using namespace std;

struct Pipe {
    int pos, up, bottom;
} pipe[10010];

const int MAXN = (1 << 30);
int n, m, k, lift[10010], down[10010], f[10010][1010];

bool cmp(Pipe a, Pipe b) {
    return a.pos < b.pos;
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i <= n - 1; i++)
        scanf("%d%d", &lift[i], &down[i]);
    for (int i = 1; i <= k; i++)
        scanf("%d%d%d", &pipe[i].pos, &pipe[i].bottom, &pipe[i].up);
    sort(pipe + 1, pipe + k + 1, cmp);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++)
            f[i][j] = MAXN;
    }
    for (int i = 1; i <= m; i++) f[0][i] = 0;
    int nump = 1;
    for (int i = 1; i <= n; i++) {
        int lower = 1, upper = m;
        if (pipe[nump].pos == i) {
            upper = pipe[nump].up - 1;
            lower = pipe[nump++].bottom + 1;
        }
        for (int j = 1; j <= upper; j++) { // 上升
            for (int k = j - lift[i - 1]; k <= m; k++) {
                if (k > j - lift[i - 1] && j < m) break; // 高度不是m就只做一次退出
                if (k >= 1) f[i][j] = min(f[i][j], min(f[i - 1][k], f[i][k]) + 1);
            }
        }
        for (int j = lower; j <= upper; j++) {
            if (j + down[i - 1] <= m) { // 下降
                f[i][j] = min(f[i][j], f[i - 1][j + down[i - 1]]);
            }
        }
        for (int j = 1; j <= lower - 1; j++) f[i][j] = MAXN; // 把柱子原来的最大值填回去
    }
    int minn = MAXN;
    bool flag = false;
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            if (f[i][j] != MAXN) {
                flag = true;
                minn = min(minn, f[i][j]);
            }
        }
        if (flag) {
            if (i == n) {
                printf("1\n%d", minn);
                return 0;
            }
            else {
                for (int j = k; j >= 1; j--) {
                    if (i >= pipe[j].pos) {
                        printf("0\n%d", j);
                        return 0;
                    }
                }
            }
        }
    }
    printf("0\n0");
    return 0;
}