大事件

题目

爱看热闹是人的本性。

小J和小R听说江安校区发生了很多大事件，作为计算机小喇叭的他们想要第一时间去打现场看看到底发生了什么。

小J："这么多事件都发生在了不同的地方，每一件都去打听我的精力也不够啊。"

小R："那你必须要放弃其中的一些事件了。"

小J："那我让想想我最多可以打听到多少件事情呢。"

这一天，在江安校区发生了N起大事件，第i起大事件发生在坐标(Xi,Yi)处。

小J从坐标(0,0)处出发，按照事件发生的时间顺序前往各个事件发生地收集资料，最后回到坐标(0,0)处。

虽然小J的速度很快，但是小J只会横冲直撞，换句话说，小J的移动必须平行于某条坐标轴。而且小J的力量是有限的，小J移动的总距离不能超过D。

所以小J不得不放弃一些大新闻的资料收集。请帮小R预测一下，小J最多可以收集多少起大事件的资料？

输入：第一行一个非负整数N，表示大事件的数量。接下来N行，每行两个整数Xi和Yi，表示第i起大事件发生地的坐标。按照大事件发生的时间顺序给出各个坐标。接下来一行一个非负整数D，表示小J移动的总距离的限制。
输出：输出一个整数，表示小J最多能收集多少起大新闻的资料。

样例1：

3
1 1
2 2
1 1
7

2

说明：如果小J收集3起大事件的资料，移动的总距离为8。小J可以选择收集事件1和事件3的资料，移动的总距离为4。

样例2：

6
-1 0
1 0
-1 0
1 0
-1 0
1 0
4

4

说明：小J可以选择收集事件1、事件2、事件4和事件6的资料，移动的总距离为4。

提示：对于 50% 的数据，保证 N≤20。对于 100% 的数据，保证 N≤100，D≤10¹⁸，|Xi|≤10⁹，|Yi|≤10⁹。

思路

选事件的顺序固定，只能跳过不能倒序，属于"有序子集最优化"。定义 dp[i][k] = 最后停在事件 i、共选 k 个时从原点到 i 的最小路程，枚举上一个事件 j < i 转移，最终找最大 k 使得所有终点中最优路程加回程 ≤ D。

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

int main() {
    int n;
    cin >> n;
    vector<long long> x(n+1), y(n+1);
    for (int c = 1; c <= n; c++) cin >> x[c] >> y[c];
    long long d;
    cin >> d;

    auto dist = [&](int a, int b) -> long long {
        long long ax = (a == 0) ? 0 : x[a];
        long long ay = (a == 0) ? 0 : y[a];
        return abs(x[b]-ax) + abs(y[b]-ay);
    };

    const long long INF = 1e18;
    vector<vector<long long>> dp(n+1, vector<long long>(n+1, INF));

    for (int c = 1; c <= n; c++)
        dp[c][1] = dist(0, c);

    for (int k = 2; k <= n; k++)
        for (int c1 = 1; c1 <= n; c1++)
            for (int c2 = c1+1; c2 <= n; c2++)
                if (dp[c1][k-1] != INF)
                    dp[c2][k] = min(dp[c2][k], dp[c1][k-1] + dist(c1, c2));

    int ans = 0;
    for (int k = 1; k <= n; k++) {
        long long best = INF;
        for (int c = 1; c <= n; c++)
            best = min(best, dp[c][k] + dist(c, 0));
        if (best <= d) ans = k;
    }

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

复杂度分析

• 时间复杂度：O(N³)，三层循环枚举 k、c1、c2
• 空间复杂度：O(N²)，dp 数组

← 返回菜鸟的coding