【牛客】生蚝接柿子（单调队列dp）

链接：G-生蚝接柿子_"夜莺杯"武汉理工大学第四届新生程序设计竞赛 (nowcoder.com)

去年新生赛的一道题。

现在补一下。

分析

不难定义出状态dp[i][j]表示，到从下往上第i个柿子的时候，此时左手在j位置可以接到的最多柿子个数。

状态的转移也比较简单，dp[i][j] -> dp[i + 1][L ~ R]，其中L， R是可以j到达的最远的位置。

当然从i - 1转移到i也可以，只需要计算出[i - m, i + m]的最大值，其中m是可以移动的最大距离，然后转移给i即可。

这里的转移时取大转移，只需要维护区间最大值即可。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e3 + 9;
int n, v, x0, len, L = 3e3;
int f[maxn], g[maxn];

struct Point
{
	int x, y;
}p[maxn];

void work(int m)//
{
	memcpy(g, f, sizeof f);//f -> g, g = the last f
	memset(f, 0xcf, sizeof f);//f = -inf, 将所有点设为无法到达 
	
	deque<int> dq;//队列存放的是下标 
	for(int i = 1, j = 1;i <= L; ++ i)//枚举左端点, 维护[i - m, i + m]最大值 
	{
		while(j <= L && j <= i + m)
		{
			//调整位置,将队尾小的弹出 
			while(!dq.empty() && g[j] >= g[dq.back()])dq.pop_back();
			dq.push_back(j ++);
		}
		
		//将不符合要求的队头弹出，如果下标不在[i - m, i + m]就不符合要求 
		while(dq.front() < i - m)dq.pop_front();
		
		//队头维护的是[i - m, i + m]最大值,也就是f[i]的新值，单调队列保证dq不为空 
		f[i] = g[dq.front()];
	}
	
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> v >> x0 >> len;
	
	for(int i = 1;i <= n; ++ i)cin >> p[i].x >> p[i].y;
	
	sort(p + 1,p + 1 + n, [](const Point &a, const Point &b)
	{
		return a.y < b.y;
	});
	
	memset(f, 0xcf, sizeof f);//初始化为-inf，表示手到不了 
	f[x0] = 0;//手能到，能拿到0个柿子
	
	int la = 0;
	for(int i = 1;i <= n; ++ i)
	{
		work((p[i].y - la) * v);
		//状态转移 
		for(int j = 1;j <= L; ++ j)
			if(j <= p[i].x && p[i].x <= j + len - 1)f[j] ++;
			
		la = p[i]. y;
	}
	
	
	int ans = 0;
	for(int i = 1;i <= L; ++ i)ans = max(ans, f[i]);
	cout << ans << '\n';
	return 0;
}