CF 1427C The Hard Work of Paparazzi

题目描述

https://codeforces.com/contest/1427/problem/C

Solution

首先我们能够想到最朴素的 $dp$ 方程

$f_i=max\lbrace f_j\rbrace+1,j<i,t_i-t_j\ge |x_i-x_j|+|y_i-y_j|$

注意到转移的限制非常大

但是题目中 $t_i$ 递增，且 $|x_i-x_j|+|y_i-y_j|\le 998$

那么对于某一个 $j$，如果 $t_i-t_j\ge 998$，那么一定能从 $j$ 转移到 $i$

而需要进行判断的只有 $t_i-t_j<998$ 的情况，因为 $t_i$ 严格递增，所有最多只有 $997$ 个

对于这些我们只需要暴力枚举，其它的存一个前缀最大值即可

时间复杂度 $O(1000n)$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#define maxn 1000010
#define pb push_back
using namespace std;

int n, m;

struct node {
    int t, x, y;
} a[maxn];

int f[maxn], ans, mx = -1;
int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].t >> a[i].x >> a[i].y;
    int k = 0; a[0].t = 0; a[0].x = a[0].y = 1; memset(f, -1, sizeof f); f[0] = 0;
    for (int i = 1; i <= n; ++i) {
        while (a[k + 1].t + 2 * m - 2 <= a[i].t) mx = max(mx, f[k++]);
        if (~mx) f[i] = mx + 1; 
        for (int j = k; j < i; ++j)
            if (~f[j] && a[i].t - a[j].t >= abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y))
                f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]); 
    } cout << ans << endl;
    return 0;
}