题目描述

解题思路

这个题目其实可以从二维问题转换成一个线性dp问题，只需要从1-m个给出的每个鼹鼠出现的信息，找出一个最长的子序列，这个子序列满足，相邻操作是可以满足移动要求的。我们相邻两个操作只要满足两个点的曼哈顿距离小于或者等于时间差，就可以移动。
dp[i][j]：从1-i个操作序列中选，以j结尾的最长序列长度。
题目需要将二维优化成一维。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.io.*;
import java.util.*;

class Main{
    public static int N = 10010;
    public static int[] dp = new int[N];
    public static int[][] pa = new int[20][20];
    public static Opration[] ops = new Opration[N];
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static boolean check(int t1,int t2){
        return Math.abs(ops[t2].t - ops[t1].t) >= (Math.abs(ops[t2].x - ops[t1].x) + Math.abs(ops[t2].y - ops[t1].y));
    }

    public static void main(String[] args)throws Exception{

        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]),m = Integer.parseInt(s1[1]);

        for(int i = 1;i <= m;i++){
            String[] s2 = br.readLine().split(" ");
            int time = Integer.parseInt(s2[0]),x = Integer.parseInt(s2[1]),y = Integer.parseInt(s2[2]);
            ops[i] = new Opration(time,x,y);
        }
        Arrays.fill(dp,1);

        for(int i = 2;i <= m;i++){
            for(int j = 1;j < i;j++)
                if(check(j,i)){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
        }


        int res = 0;
        for(int i = 1;i <= m;i++) res = Math.max(dp[i],res);
        System.out.print(res);

    }

    static class Opration{
        int t,x,y;
        public Opration(int t,int x,int y){
            this.t = t;
            this.x = x;
            this.y = y;
        }
    }
}