跳房子（单调队列优化DP）

本文主要是介绍跳房子（单调队列优化DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

重点

for(int i=1;i<=n;i++)
{while(x[i]-x[j]>=l&&j<i){if(f[j]!=-0x7fffffff){while(h<=t&&f[q[t]]<=f[j])t--;q[++t]=j;}j++;}while(h<=t&&x[i]-x[q[h]]>r)h++;if(h<=t)f[i]=f[q[h]]+s[i];
}

完整代码

#include<bits/stdc++.h>
using namespace std;
int n,d,k,x[500001],s[500001],ans,q[500001];
long long sum,f[500001];
long long dp(int l,int r)
{long long cc=0;int h=1,t=0,j=0;memset(f,-0x7f,sizeof(f));memset(q,0,sizeof(q));f[0]=0;for(int i=1;i<=n;i++){while(x[i]-x[j]>=l&&j<i){if(f[j]!=-0x7fffffff){while(h<=t&&f[q[t]]<&#

这篇关于跳房子（单调队列优化DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---