alpcOj Journey to the The World's Start-蒲公英云

alpcOj Journey to the The World's Start

题目链接：http://oj.alpc.cn/en/Problem/Details?cid=17&tid=J

Jerry Prince is the fourth grade student and he goes to New-Lodnon to visit the most popular amusement park “The World’s Start”.

An airport he arrives at is next to the first stop of the metro line. This line has n stops and “The World’s Start” is on the last of them. The metro of New-Lodnon is pretty fast so you may assume that you can get from a stop to the next one in just one minute.

题目大意：有从左到右有1-n共n个车站，有n-1种车票，每种票有固定的价钱，每种最多可以坐1-(n-1)站，每个人只能持有一种车票，下车后可以继续上车（每次上车后可以中途下车，但最多做车票对应的站数），但每次下车都要再上车都要花费一定时间，第1和n站上车不花费时间，车从每行进一站需要一分钟，问在t时间内从1-n站话费的票价最低是多少。

解题思路：
这道题的关键在于如何求每种票到达终点所需的最少时间，如果找出了每种票到车站的最少时间，再直接判断哪种票最便宜就好了。

对于求每种票的时间，最直观的想法是对每一种票进行dp，设dp[i]为到i站所需的最少时间，L为此票最多能乘坐的站数，time[i]为在此站下车又上车的时间。
dp[i]=min(dp(i-t))+time[i] 1<=t<=i-L
对于n-1种票，每种票枚举n个车站，枚举到每个车站时还要向前推L个，复杂度为n^3

但我们会发现，车票行进距离越大，所需的总时间越小，因为假设n站的最优解（也就是最优停车位置已定），n+1站的车票也能在相应的停车位置停车，反之则不能，所以n+1站一定包含n站最优解。这样我们就可以二分查找所需时间小于等于t-(n-1)的车票就好了。复杂度n^2*logn

对于每次dp，我们找区间中的最小值时，可以采用单调队列的方法来计算区间最小值，这里因为要根据位置判断是否剔除，所以我在单调区间里保存的是位置，详情见代码。复杂度n*logn 。

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <functional>
#define RI(N) scanf("%d",&(N))
#define RII(N,M) scanf("%d %d",&(N),&(M))
#define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
#define mem(a) memset((a),0,sizeof(a))
using namespace std;
const int inf=1e9;
const int inf1=-1*1e9;
double EPS=1e-10;
typedef long long LL;
int price[55005];
int time[55005];
int que[55005];
int n,t;
LL dp[55005];
int main()
{
    RII(n,t);
    t-=(n-1);
    LL sum=0;
    for(int i=1; i<n; i++)
    {
        RI(price[i]);
    }
    for(int i=2; i<=n-1; i++)
    {
        RI(time[i]);
        sum+=time[i];
    }
    time[n]=0;
    int l=1, r=n-1;//车票的站数
    while(r-l>1)
    {
        int mid=(r+l)>>1;
        int ll=1,rr=0;//单调区间的左值和右值
        dp[1]=0;
        que[1]=inf;//que数组保存单调区间里的值，注意值是位置
        for(int i=2;i<=n;i++)
        {
            //判断是否要剔除单调区间里的值
            if(i-que[ll]>mid)  ll++;
            //如果新加了一个小值 则向前覆盖
            while(rr>=ll&&dp[i-1]<=dp[que[rr]]) rr--;
            que[++rr]=i-1;//每次单调区间里的值增加一个
            //更新dp[i]
            dp[i]=dp[que[ll]]+LL(time[i]);
        }
        if(dp[n]>t) l=mid;
        else r=mid;
    }
    int ans;
    //按我的二分方法l==1可能统计不到，这里进行特判
    if(sum<=t) {
            ans=price[1];
        r=1;
    }
    else ans=price[r];
    for(int i=r+1;i<=n-1;i++)
    {
        ans=min(ans,price[i]);
    }
    printf("%d\n",ans);
    return 0;
}