RT，之前一直没学会单调队列优化dp，刚才写了一个不知道为什么不对，能有大佬抽点时间帮忙看一下吗？

错误代码的check函数

void mem()
{
	memset(dp,0x80,sizeof dp);
	memset(q,0,sizeof q);
	dp[0] = 0;
}
bool check(int x1,int x2)
{
	mem();
	int j = 0;
	int head = 1,tail = 0;
	for(int i = 1;i <= n;i++)
	{
		if(dis[i]<x1) continue;
		while(head <= tail&&dp[q[tail]]  <= dp[j]) tail--;
		q[++tail] = j;
		while(head <= tail&& dis[q[head]] + x2 < dis[i])
		{
			head++;
		} 
		dp[i] = dp[q[head]] + a[i];
		j++;
	}
	for(int i = 1;i <= n;i++) if(dp[i] >= k) return 1;
	return 0;
}

把这个改成这样就对了

bool check(int x1,int x2)
{
	mem();
	int j = 0;
	int head = 1,tail = 0;
	for(int i = 1;i <= n;i++)
	{
		while(dis[i] - dis[j] >= x1 && j < i)
		{
			if(dp[j]!=-1)
			{
				while(head<= tail && dp[q[tail]] <= dp[j]) tail--;
				q[++tail] = j;
			}
			j++;
		}
		while(head <= tail&& dis[q[head]] + x2 < dis[i])
		{
			head++;
		} 
		if(head <= tail)dp[i] = dp[q[head]] + a[i];
	}
	for(int i = 1;i <= n;i++) if(dp[i] >= k) return 1;
	return 0;
}

$x_1,x_2$ 表示跳跃的最小，最大距离