小红和苹果树

[题目链接](https://www.nowcoder.com/practice/aba1a8a8d30f49619ce195d2a09029db)

思路

问题建模

苹果 的位置为 ，从第 秒开始下落，每秒下落 1 个单位，因此苹果到达 的时刻为：

$$

小红从时刻 出发，初始位置为 ，每秒最多移动 个单位。

小红能同时被苹果 和苹果 （设 ）砸到，当且仅当她能在时刻 到达 ，又在时刻 到达 ，即：

$$

此外，从初始位置 在时刻 到达 的条件为：

$$

转化为 DP

将问题转化为：在所有苹果中，找一个最长子序列，使得按 排序后相邻两个苹果均可连续到达，且从起点出发可以到达第一个苹果。

这与「最长递增子序列（LIS）」的框架一致：

• 按 升序排序苹果
• 定义 = 以苹果 为最后一个被砸到的苹果时，最多能被砸到的苹果数

转移方程：

$$

dp[i] = \max_{j < i,\, dp[j] > 0,\, |x_i - x_j| \le T_i - T_j} (dp[j] + 1)

$$

初始化：若 （可从起点直接到达），则 的初始值为 ，否则为 （不可从起点到达）。

答案：。

时间复杂度 ，空间复杂度 。

样例分析

输入：

3
1 1 1
2 1 1
4 1 3

三颗苹果的到达时刻：

• 苹果1：，
• 苹果2：，
• 苹果3：，

排序后（ 相同时顺序无关）：

• 苹果1：，，可达，
• 苹果2：，，可达，；但苹果1和苹果2同时到达（ 不成立），无法转移
• 苹果3：，，可达，；从苹果1： 不成立；从苹果2： 成立，

答案为 ，与样例一致。

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<pair<long long, long long>> apples(n); // (T, x)
    for (int i = 0; i < n; i++) {
        long long x, y, t;
        cin >> x >> y >> t;
        apples[i] = {t + y, x};
    }

    sort(apples.begin(), apples.end());

    vector<int> dp(n, 0);
    int ans = 0;

    for (int i = 0; i < n; i++) {
        long long Ti = apples[i].first;
        long long xi = apples[i].second;

        if (abs(xi) <= Ti) dp[i] = 1;

        for (int j = 0; j < i; j++) {
            if (dp[j] == 0) continue;
            long long Tj = apples[j].first;
            long long xj = apples[j].second;
            if (abs(xi - xj) <= Ti - Tj) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        ans = max(ans, dp[i]);
    }

    cout << ans << endl;
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());

        long[][] apples = new long[n][2]; // [T, x]
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());
            long t = Long.parseLong(st.nextToken());
            apples[i][0] = t + y;
            apples[i][1] = x;
        }

        Arrays.sort(apples, (a, b) -> Long.compare(a[0], b[0]));

        int[] dp = new int[n];
        int ans = 0;

        for (int i = 0; i < n; i++) {
            long Ti = apples[i][0];
            long xi = apples[i][1];

            if (Math.abs(xi) <= Ti) dp[i] = 1;

            for (int j = 0; j < i; j++) {
                if (dp[j] == 0) continue;
                long Tj = apples[j][0];
                long xj = apples[j][1];
                if (Math.abs(xi - xj) <= Ti - Tj) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            ans = Math.max(ans, dp[i]);
        }

        System.out.println(ans);
    }
}