C++(clang++ 11.0.1) 解法, 执行用时: 108ms, 内存消耗: 604K, 提交时间: 2022-11-06 21:27:25

#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 = 0
	
	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.empty() && dq.front() < i - m)dq.pop_front();
		
		//队头维护的是[i, i + m]最大值,也就是f[i]和f[i + m]的新值 
		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);
	f[x0] = 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;
}

C++(g++ 7.5.0) 解法, 执行用时: 76ms, 内存消耗: 592K, 提交时间: 2022-11-20 11:49:25

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x7f7f7f7f;
struct node
{
    int x,y;
    bool operator< (const node &b) const {return y < b.y;}
}ar[3005];
int dp[3005],f[3005];
int que[3005];
int n,v,x0,len;
void getmax(int m)
{
    for(int i=1;i<=3000;i++)
        f[i] = dp[i];
    int head = 1,tail = 0;
    for(int i=1,j = 1;i<=3000;i++)
    {
        while(j <= min(3000,i+m))
        {
            while(head <= tail && f[que[tail]] <= f[j])
                tail--;
            que[++tail] = j++;
        }
        while(que[head] < i - m) head++;
        dp[i] = f[que[head]];
    }
}
void solve()
{
    scanf("%d%d%d%d",&n,&v,&x0,&len);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&ar[i].x,&ar[i].y);
        f[i] = dp[i] = -INF;
    }
    dp[x0] = 0;
    sort(ar+1,ar+n+1);
    for(int i=1;i<=n;i++)
    {
        int r = (ar[i].y - ar[i-1].y) * v;
        getmax(r);
        for(int j=1;j<=3000;j++)
            if (j <=ar[i].x && j+len-1 >= ar[i].x)
                dp[j]++;
    }
    int ans = 0;
    for(int i=1;i<=3000;i++)
        ans = max(ans,dp[i]);
    printf("%d\n",ans);
    
}

int main()
{
    solve();
}