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

其实我在写到一半的时候就突然想到我的状态转移方程是错的,然而还是抱着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;
}
Categories: 简单DP

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

简单DP

HDU 6143 Killer Names

昨天的多校应该是团队合作最失败的一次…… 一开始过题人数最多的那道题许 Read more…

简单DP

HDU 5074 Hatsune Miku

老实说有点崩溃,一场训练赛,3道dp都没出,两道还是全世界都A了 毫无 Read more…

简单DP

POJ 1692 Crossed Matchings

坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑 Read more…