首先我们二分一个x，x是用的票能跳过x站，因为票可以多次使用，所以我们要dp当第i站能用票省下的时间p，只要p小于等于 （不用票的总时间-t）就好了
这个dp我们可以写出转移方程 dp[i]=\(max_{j=i-x}^{j=i}\)(d[j]+s[i]-s[j],(s是前缀和)
但是这个dp是\(n^2\)的，所以我们需要用单调队列优化
代码
#include<stdio.h>
#define LOCAL
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5+10;
ll p[maxn],d[maxn],a[maxn],dp[maxn],q[maxn];ll n,t,sum,mi=1e9;
ll pd(ll mid)
{
memset(q,0,sizeof(q));ll l=1,r=0,mx=0;
memset(dp,0,sizeof(dp));
q[++r]=1;
for(ll i=2;i<=n;i++)
{
while(l<=r&&(i-q[l])>mid) l++;
//printf("i=%lld q[%lld]=%lld\n",i,l,q[l]);
dp[i]=dp[q[l]]+a[i-1]-a[q[l]];
mx=max(dp[i],mx);
while(l<=r&&(dp[i]-a[i]>=dp[q[r]]-a[q[r]])) r--;
q[++r]=i;
//printf("dp[%lld]=%lld q[%lld]=%lld q[%lld]=%lld\n",i,dp[i],l,q[l],r,q[r]);
}
if(mx>=sum) return 1;
return 0;
}
int main()
{
#ifdef LOCAL
freopen("journey.in","r",stdin);
freopen("journey.out","w",stdout);
#endif
scanf("%lld %lld",&n,&t);
sum=n-1;
for(int i=1;i<=n-1;i++)
{
scanf("%lld",&p[i]);mi=min(p[i],mi);
}
for(int i=2;i<=n-1;i++) scanf("%lld",&d[i]),sum+=d[i];
if(sum<=t)
{
printf("%lld\n",mi);
return 0;
}
sum=sum-t;
ll l=1,r=n-1,len=0;
for(ll i=2;i<=n;i++) a[i]=a[i-1]+d[i];
//pd(1);
while(l<=r)
{
ll mid=(l+r)/2;
if(pd(mid)==1)
{
len=mid;
r=mid-1;
}
else l=mid+1;
}
ll g=1e9;
for(int i=len;i<=n-1;i++) g=min(g,p[i]);
printf("%lld\n",g);
//printf("sum=%d\n",sum);
/*ll s=0,l=1,r=1;
ll len = n+10;
while(l<=r&&l<=n-1&&r<=n)
{
int flag=0;
while(s<sum){
s+=1+d[r];
r++;
if(r>n){
flag=1;
break;
}
}
if(flag==1)break;
len=min(len,r-l);
printf("s=%lld l=%lld r=%lld\n",s,l,r);
if(l+1<r)
s-=d[l+1]+1;
else s--;
l++;
}
printf("len=%lld\n",len);
ll g = 1e9;
for(ll i = len; i <= n-1; i++){
g=min(g,p[i]);
}
printf("%lld\n",g);*/
}
/*
4 4
1 2 3
1 4
6 6
1 4 5 5 6
7 1 5 6
*/
2015-2016 ACM-ICPC, NEERC, Northern Subregional Contest Journey to the "The World's Start"
原文：https://www.cnblogs.com/League-of-cryer/p/14001826.html