Gym100810J Journey to the "The World's Start" （二分答案+动态规划）

  • 题目链接

  • 题目大意：现有n个车站，从1号车站出发，目的地为n号车站，相邻两个车站间路程消耗时间为1。但乘车需要乘车卡（一张乘车卡可以无限用但有最大连续车站限制），从中间车站下车再上车需要等待时间。现给出n-1张乘车卡的价格（第i张卡可以连续坐i站，之后需要下车再上车）和中间n-2个站点下车需要等待的时间。问能否在总时间不超过t的限制下找出最少花费，其中t >= n-1，即保证有答案。

  • 思路：首先我们知道，如果有两张可乘坐长度为a和b的卡（a < b），那么卡b是可以当做卡a使用的，即如果卡i能满足t时间限制，那么i至n-1的所有卡都能满足t时间限制，我们需要找到最小的i，取区间i到n-1中最便宜的卡即可，因此可以使用二分答案处理。 二分答案需要判断在给定最长连续乘坐长度len的情况下，能否满足时间t的限制。我们用dp[i]表示到达第i个车站需要消耗的最小等待时间，如果所有车站的dp值都小于等于t - (n - 1)，说明符合要求。同时得到状态转移方程dp[i] = min(dp[j] + d[j])，表示从第j站下车后再上车到达第i站，d[j]为车站等待时间，i - j <= len。 由于时间限制，需要使用单调队列或者线段树维护指定区间dp[j]+d[j]的最小值。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int N = 5e4 + 10;
int p[N], d[N], n;
ll dp[N], t;

bool solve(int len) {
    memset(dp, 0, sizeof(dp));
    deque < pair >q;
    q.push_back(make_pair(0, 1));
    for (int i = 2; i <= n; i++) {
        //单调队列清除不符合区间要求的元素
        while (!q.empty() && q.front().second + len < i) q.pop_front();
        dp[i] = q.front().first;
        if (dp[i] > t - (n - 1)) return false;
        if (i == n) break;
        //清除比要插入元素优先级小的元素以维护单调队列
        while (!q.empty() && q.back().first >= dp[i] + d[i]) q.pop_back();
        q.push_back(make_pair(dp[i] + d[i], i));
    }
    return true;
}

int main(int argc, char const *argv[]) {
    ios::sync_with_stdio(false);
    freopen("journey.in", "r", stdin);
    freopen("journey.out", "w", stdout);
    while (cin >> n >> t) {
        for (int i = 1; i < n; i++) cin >> p[i];
        for (int i = 2; i < n; i++) cin >> d[i];
        for (int i = n - 2; i; i--) p[i] = min(p[i], p[i+1]);//令p[i]为后缀区间中的最小值
        int res = 0, l = 1, r = n - 1;
        while (r >= l) {
            int mid = (l + r) >> 1;
            if (solve(mid) == true) {
                res = p[mid];
                r = mid - 1;
            } else l = mid + 1;
        }
        cout << res << endl;
    }

    return 0;
}
单调队列二分答案动态规划

相关

单调队列优化DP历险记

动态规划-------最短路径问题

背包问题c++动态规划方式

单调队列

[ZJOI2009]对称的正方形 manacher+单调队列

动态规划之矩阵连乘

动态规划 BZOJ1801 [Ahoi2009]chess 中国象棋

线性规划和动态规划

【学习笔记】动态规划—矩阵递推加速

[LeetCode]1320. Minimum Distance to Type a Word Using Two Fingers 动态规划解法

123. 买卖股票的最佳时机 III——动态规划-股票收益问题

最佳观光组合——动态规划

标签