Menu
Article ACM

POJ 1661 Help Jimmy

NodeKey

NodeKey

• 3 min read

好题！！！！
这道题我整整想了一个晚上，怎么说呢，应该还是我从一开始就没想复杂，考虑得简单了，然后后面就写的很复杂了……

其实我在写到一半的时候就突然想到我的状态转移方程是错的，然而还是抱着poj数据弱的侥幸继续写下去……然后错误的地方越写越清晰……

题意：
一个90后都玩过的空间游戏吧，记得叫 是男人就下一百层 ，题意不是很好描述，可以自己去玩玩。

思路：
先说一下我最开始的想法，不想看的直接往下翻。
这道题我一看，诶，水题！我只要每次移动都保证当前层所花时间最少，类似记忆化搜索，一步一步推过去就能保证我的答案最优……

首先这个思路的确是对的，但却忽略了一个细节，从我以前走过的层到我当前层，有个位置上的关系。
就是说当我每次得到当前层时间最短的时候，我必须把落下的相应位置给确定下来，否则，若存在重复的最优时间，当前下落位置不同，会影响之后的时间。这是显然的。
而我要想补救我的思路，那我必须记录所有的位置，虽然这个位置数量不会超过2，但这实现起来就很烦。

正解：
其实正解是很简单的，我只要反向思考就可以了。就是记录当前层到底层的最短时间。考虑当前层到中间层再到底层，则中间层的起始位置必定是当前层的两边。若不存在中间层。则时间为高度，其实这个可以省略

所以只要考略每层的两边是否能到中间层即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int inf = 0x3f3f3f3f;

struct node {
    int l, r, h;
    bool operator<(const node& a) const { return h < a.h; }
} s[1005];

int dp[1005][2];
int main()
{
    int n, t, x, y, limit;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d%d", &n, &x, &y, &limit);
        s[0].l = s[0].r = x, s[0].h = y;
        range(i, 1, n) scanf("%d%d%d", &s[i].l, &s[i].r, &s[i].h);
        sort(s, s + n + 1), fill(dp, 0);
        each(i, n + 1)
        {
            bool flag = false;
            reach(j, i) if (s[i].h - s[j].h <= limit && s[i].l >= s[j].l && s[i].l <= s[j].r)
            {
                dp[i][0] = min(dp[j][0] + s[i].l - s[j].l, dp[j][1] + s[j].r - s[i].l);
                flag = true;
                break;
            }
            if (!flag)
                dp[i][0] = s[i].h - s[0].h > limit ? inf : 0;
            flag = false;
            reach(j, i) if (s[i].h - s[j].h <= limit && s[i].r >= s[j].l && s[i].r <= s[j].r)
            {
                dp[i][1] = min(dp[j][0] + s[i].r - s[j].l, dp[j][1] + s[j].r - s[i].r);
                flag = true;
                break;
            }
            if (!flag)
                dp[i][1] = s[i].h - s[0].h > limit ? inf : 0;
        }
        printf("%d\n", min(dp[n][0], dp[n][1]) + y);
    }
    return 0;
}
Share