/doge薛昊老是偷我题做,最近我也就拿他博客上的题来练练手。其中这道题真的什么思路都没有,这个区间DP的套路我还真没碰到过。

这是一个大区间推小区间的套路。

题意:
小明要在某层楼的各个老师那里交一大堆作业,但是小明来早了,老师还没上班,他站在这层楼的最左边,告诉你每个老师的上班时间,最后要在某个给定位置下楼,问最少时间。

思路:
shit,完全是看博客,看代码敲的。
一个比较困难的点在于给定离开地点,算了,不装了,就算取消这个条件我也写不来……
明确可以用dp求解,首先按照位置优先开门顺序次优的顺序排序,设三维数组 dp[l][r][k]
k=0 时,表示只有 (l,r] 区间内的作业没有交。
k=1 时,表示只有 [l,r) 区间内的作业没有交。
而我们的其实状态dp[1][n][0/1]是已知的,我们完全可以由此不断向内挤压求出小区间的结果。
l=r 时,则所有作业交完,且停在 l 点。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#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;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
int dp[maxn][maxn][2];
pii point[maxn];

int getDis(int d, int s) { return point[d].first - point[s].first; }

int main()
{
    int n, h, b;
    scanf("%d %d %d", &n, &h, &b);
    range(i, 1, n) scanf("%d %d", &point[i].first, &point[i].second);
    sort(point + 1, point + 1 + n);
    fill(dp, 0x3f);
    dp[1][n][0] = max(point[1].first, point[1].second);
    dp[1][n][1] = max(point[n].first, point[n].second);
    rrange(len, 1, n - 1) range(l, 1, n + 1 - len)
    {
        int r = l + len - 1;
        if (l > 1) {
            dp[l][r][0] = min(dp[l][r][0], dp[l - 1][r][0] + getDis(l, l - 1));
            dp[l][r][1] = min(dp[l][r][1], dp[l - 1][r][0] + getDis(r, l - 1));
        }
        if (r < n) {
            dp[l][r][0] = min(dp[l][r][0], dp[l][r + 1][1] + getDis(r + 1, l));
            dp[l][r][1] = min(dp[l][r][1], dp[l][r + 1][1] + getDis(r + 1, r));
        }
        dp[l][r][0] = max(dp[l][r][0], point[l].second);
        dp[l][r][1] = max(dp[l][r][1], point[r].second);
    }
    int ans = inf;
    range(i,1,n) ans = min(ans,dp[i][i][0]+abs(b-point[i].first));
    printf("%d\n",ans);
    return 0;
}
Categories: 区间DP

发表评论

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

Related Posts

区间DP

区间DP入门 —— 三类经典问题

例行废话 大概是前天试着去入门区间DP,中间穿插了很多其他题目,今天勉 Read more…