单调队列求助QAQ

由于这道题 check 函数里面的转移是找到所有 j 满足 max(d - mid, 1) <= x[i] - x[j] <= d + mid 的

dp_j

的最大值，到这里其实可以直接做了，但是我对不等式进行了进一步的转化：找到 j 满足 x[i] - d - mid <= x[j] <= x[i] - max(d - mid, 1) 的最大

dp_j

。

照理来说是等价的，但是我单调队列写的是错的：

CPP

for(int i = 1; i <= n; ++i){
	f[i] = -1e18;
	while(!q.empty() && x[q.front()] < (long long)x[i] - d - mid) q.pop_front();
	if(!q.empty() && x[q.front()] <= x[i] - max(d - mid, 1)) f[i] = f[q.front()] + s[i];
	while(!q.empty() && f[q.back()] <= f[i]) q.pop_back();
	if(f[i] > -1e18) q.push(i);
}

f

数组就是 dp 数组，开了 long long 的。

想维护的是 dp 值递减，x 值（每个点离起点的距离）递增的单调队列。

对于第一个 while 循环，不断弹出队首使得队首 x[j] >= x[i] - d - mid；对于第二个 if，如果返回 true 说明当前队首满足右边界 x[j] <= x[i] - max(d - mid, 1)，否则队首后面的 j 一定不满足，因为队列内 x 是递增的；第三个 while 就是维护 dp 值递减的；对于第四个 if，如果当前 i 是可达到的（更新过的）就放入队列。

求大佬帮忙看看 QAQ。

讨论操作

回复

相关推荐

单调队列求助QAQ