Description

鼹鼠是一种很喜欢挖洞的动物, 但每过一定的时间, 它还是喜欢把头探出到地面上来透透气的. 根据这个特点阿 Q 编写了一个打鼹鼠的游戏: 在一个 \(n \times n\) 的网格中, 在某些时刻鼹鼠会在某一个网格探出头来透透气. 你可以控制一个机器人来打鼹鼠, 如果 \(i\) 时刻 鼹鼠在某个网格中出现, 而机器人也处于同一网格的话, 那么这个鼹鼠就会被机器人打死. 而机器人每一时刻只能够移动一格或停留在原地不动. 机器人的移动是指从当前所处的网格 移向相邻的网格, 即从坐标为 \((i, j)\) 的网格移向 \((i-1, j), (i+1, j), (i, j-1), (i, j+1)\) 四个网格, 机器人不能走出整个 \(n \times n\) 的网格. 游戏开始时, 你可以自由选定机器人的初始位置. 现在你知道在一段时间内, 鼹鼠出现的时间和地点, 希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠.

Input

第一行为 \(n (n \leq 1000), m (m \leq 10000)\), 其中 \(m\) 表示在这一段时间内出现的 鼹鼠的个数, 接下来的 \(m\) 行每行有三个数据 \(time, x, y\) 表示有一只鼹鼠在游戏开始后 \(time\) 个时刻, 在第 \(x\) 行第 \(y\) 个网格里出现了一只鼹鼠.\(time\) 按递增的顺序给出. 注意同一时刻可能出现多只鼹鼠, 但同一时刻同一地点只可能出现一只鼹鼠.

Output

仅包含一个正整数, 表示被打死鼹鼠的最大数目

Sample Input

2 2
1 1 1
2 2 2

Sample Output

1

Explanation

把这个问题仔细想一想, 一个鼹鼠是突然出现的, 马上消失. 也就是说机器人如果按时走不到 那里就可以滚粗了. 所以就变成了一个最长上升子序列问题 (类型题小结) 或者类上升子序列 问题. 换句话说, 可能这道题上个 \(O(m^2)\) 就够了, 如果常数比较小的话~

黄学长说没有 \(O(m \log m)\) 的做法, 但是各种神优化 (设 max) 可以水过时限......

所以说这道题能不能 \(O(m \log m)\) 呢? 这个问题留给读者思考 (雾)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxm = 10010;

int n, m;
int t[maxm], x[maxm], y[maxm];
int dp[maxm], max_dp[maxm];

int dist(int i, int j) {
    return abs(x[i] - x[j]) + abs(y[i] - y[j]); }

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &t[i], &x[i], &y[i]);
    // Dynamic programming.
    dp[1] = 1, max_dp[1] = 1;
    for (int i = 2; i <= m; i++) {
        dp[i] = 1;
        for (int j = i - 1; j >= 1; j--) {
            if (max_dp[j] + 1 <= dp[i])
                break;
            // Potentially demands update
            if (dp[j] + 1 > dp[i])
                if (dist(i, j) <= t[i] - t[j])
                    dp[i] = dp[j] + 1;
        }
        max_dp[i] = max(max_dp[i - 1], dp[i]);
    }
    int res = 0;
    for (int i = 1; i <= m; i++)
        res = max(res, dp[i]);
    printf("%d\n", res);
    return 0;
}