[NOIP2017普及组]跳房子（二分答案+单调队列优化dp）

确实算是板子题，不难发现“二分花费，dp 求最大得分”的 \(\mathcal{O(n\log n)}\) 思路，那么式子就是：

其中 \(L=\max(1,d-g),R=d+g\)。显然符合单调队列性质。

但是在代码实现上出现了一点困难：判断 \(x_i-x_j>R\) 弹队头比较简单，如何限制 \(x_i-x_j 不能进呢？事实上，“现在不能进”说明要“过一会再进”，可以记录一个指针 \(j\)，指到已经进队的位置，每次检查哪些元素可以进队。因为每个元素仍然进出各一次，所以复杂度没有增加。

平时遇到较多的是 \(\max\limits_{i-k\le j 型的单调队列，没有见过在右侧加以限制的类型，还是做题太少了……

具体代码如下:

inline bool check(int g){
	int l=1,r=0,L=std::max(1,d-g),R=d+g;
	memset(f,0xcf,sizeof f);
	f[0]=0;
	for(int i=1,j=0;i<=n;++i){
		while(j<=n&&x[i]-x[j]>=L){
			while(l<=r&&f[q[r]]<=f[j]) --r;
			q[++r]=j,++j;
		}
		while(l<=r&&x[i]-x[q[l]]>R) ++l;
		if(l<=r) f[i]=f[q[l]]+s[i];//不再立即进队，而是改为在上方while处等待
		if(f[i]>=k) return 1;
	}
	return 0;
}

THE END