C. The Hard Work of Paparazzi (dp)

ゞ浴缸里的玫瑰 2021-07-17 01:07 290阅读 0赞

[题目][Link 1]

思路：这是一道最长递增子序列的变式。

dp\[i\] 代表前i个名人中第i个名人被访问所能访问的最大名人数目

先看暴力的方法，那么我们直接遍历前面所有情况

当abs(x\[i\]-x\[j\])+abs(y\[i\]-y\[j\])<=t\[i\]-t\[j\] i<j 时dp\[i\]=max(dp\[i\],dp\[j\]+1)

但这时时间复杂度O(n^2) 会超时，我们需要优化一下

这时我们发现最大的距离不会超过2*r-2，而对于每个名人出场的时间是递增的，也就是说一旦出场的名人相隔超过2*r-2位那么他们相隔时间也超过了2*r-2，那么对于一个事件来说我们只需要对2*r-2个事件内进行遍历判断，在这之前的事件我的时间间隔一定超过2\*r-2，都是满足的直接取最大值即可，用一个数组记录即可,时间复杂度O(n \* r)。

if(i-j>=2*r-2) dp\[i\]=max(dp\[i\],max\[i-2*r-2之前最大的dp\[j\]\]+1)  
if(i-j<=2\*r&&abs(x\[i\]-x\[j\])+abs(y\[i\]-y\[j\])<=t\[i\]-t\[j\] ) dp\[i\]=max(dp\[i\],dp\[j\]+1)

#include<iostream>
    #include<cmath>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int Mod = 1e9 + 7;
    int x[Max], y[Max], t[Max];
    int dp[Max], ma[Max];
    
    int main()
    { 
    	FAST;
    	int r, n;cin >> r >> n;
    	for (int i = 1;i <= n;i++) dp[i] = -1e9;
    	for (int i = 1;i <= n;i++) cin >> t[i] >> x[i] >> y[i];
    	x[0] = 1, y[0] = 1;
    	int ans = 0;
    	for (int i = 1;i <= n;i++)
    	{ 
    		if (i - 2 * r >= 0)dp[i] = ma[i - 2 * r] + 1;
    		for (int j = max(0, i - 2 * r);j <= i - 1;j++)
    		{ 
    			if (abs(x[i] - x[j]) + abs(y[i] - y[j]) <= t[i] - t[j]) dp[i] = max(dp[i], dp[j] + 1);
    		}
    		ma[i] = max(ma[i - 1], dp[i]);
    		ans = max(ans, dp[i]);
    	}
    	cout << ans << endl;
    }

[Link 1]: https://codeforc.es/problemset/problem/1427/C