#二分，单调队列，动态规划#洛谷 3957 跳房子

本文主要是介绍#二分，单调队列，动态规划#洛谷 3957 跳房子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

---

分析

$f[i]表示跳到i时的最大值$，很容易可以得到
f [ i ] = m a x { f [ l a s t ] } + s [ i ] f[i]=max\{f[last]\}+s[i] f[i]=max{f[last]}+s[i]，然而也很容易知道需要用单调队列维护,但是求到答案又能怎么做，二分答案，于是代码就出来了。

---

代码

#include <cstdio>
#include <cctype>
using namespace std;
int n,d,k,dis[500001],s[500001],f[500001],q[500001];
int in(){int ans=0,f=1; char c=getchar();while (!isdigit(c)&&c!='-') c=getchar();if (c=='-') c=getchar(),f=-f;while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans*f;
}
int max(int a,int b){return (a>b)?a:b;}
bool check(int g){int p=0,head=1,tail=0; q[1]=0;for (int i=1;i<=n;i++) f[i]=-1<<31;for (int i=1;i<=n;i++){while (dis[i]-dis[p]>=max(d-g,1)&&p<i){while (f[q[tail]]<=f[p]&&head<=tail) tail--;q[++tail]=p++;}while (dis[i]-dis[q[head]]>d+g&&head<=tail) head++;if (head>tail||f[q[head]]==-1<<31) continue;else f[i]=f[q[head]]+s[i];if (f[i]>=k) return 1;}return 0;
}
int main(){n=in(); d=in(); k=in();for (int i=1;i<=n;i++) dis[i]=in(),s[i]=in();int l=0,r=1e9,ans=-1; while (l<r){int mid=(l+r)>>1;if (check(mid)) ans=r=mid; else l=mid+1;}printf("%d",ans);
}

这篇关于#二分，单调队列，动态规划#洛谷 3957 跳房子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---