洛谷 P4766 分析（别看）

科技起源

2026-07-17 14:38:25

发布于：河北

3阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：有 $n$ 个外星人，每个外星人 $i$ 离你的距离为 $d_i$ ，它在时刻 $a_i$ 出现，需要在 $b_i$ 之前被消灭。
允许：你的位置是固定的，可以在任意时刻使用一次武器，武器的功率 $R$ 是可以自己设置的，效果就是可以消灭当前时刻在外星人出现区间时间在 $[a_i,b_i]$ 且和你距离 $\le R$ 的所有外星人。每次使用花费代价为 $R$ ，求所有外星人被消灭的最小花费
禁止：
限制：

1.3 题目数据范围与猜测

$1 \le n \le 300 \longrightarrow O(n^3)$

1.4 一句话概括题意

有一些外星人，位置及出现时间区间各不相同，求把所有外星人消灭的最小花费

2 题目破题推导

我们只考虑时间区间 $[L,R]$ 里的所有外星人：
如果一个外星人的出现时间 $[a_i,b_i]$ 完全被 $[L,R]$ 包含在内，那么就代表这个外星人必须要在时间 $[L,R]$ 内被消灭。而我们需要找到所有这样的外星人，最终，这段时间消灭所有外星人的最小花费一定就是所有这段时间的外星人离的最远距离 $mx$ （“我”的位置始终固定）
那么其他外星人呢？也就是说，当我们在时间 $[L,R]$ 之间的某个时刻 $k$ 发射了功率为 $mx$ 的炮，那出现时间被 $[L, k-1]$ 和 $[k+1,R]$ 两个区间完全包围的所有外星人都是攻击不到的，需要继续考虑那两个区间
最终，总花费为 $mx+min(消灭[L, k-1]外星人花费) + min(消灭[k+1,R]外星人花费)$

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：动态求取最小值，区间 $\longrightarrow$ $\huge{区间dp}$
因为一般来说，区间dp需要 $dp[l][r]$ ，这题的时间范围 $\le 10000$ ，会MLE，因此还需要把时间 $\huge{离散化}$ 再dp

4 最终代码（禁止抄袭，仅用于参考）

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

const int N = 333;
const int INF = 0x3f3f3f3f;
int a[N], b[N], d[N];
int l[N], r[N];
int dp[N * 2][N * 2];
int t;

signed main(){

    cin >> t;
    while(t--){
        int n;
        cin >> n;
        set<int> s;
        for (int i = 1;i <= n;i++){
            cin >> a[i] >> b[i] >> d[i];
            s.insert(a[i]);
            s.insert(b[i]);
        }
        int m = s.size();
        vector<int> times;
        for (int num : s){
            times.push_back(num);
        }
        for (int i = 1;i <= n;i++){
            l[i] = lower_bound(times.begin(), times.end(), a[i]) - times.begin() + 1;
            r[i] = lower_bound(times.begin(), times.end(), b[i]) - times.begin() + 1;
        }
        memset(dp, 0x3f, sizeof(dp));
        for (int len = 1;len <= m;len++){
            for (int left = 1;left + len - 1 <= m;left++){
                int right = left + len - 1;
                int mx = -INF;
                for (int i = 1;i <= n;i++){
                    if (l[i] >= left && r[i] <= right){
                        mx = max(mx, d[i]);
                    }
                }
                if (mx == -INF){
                    dp[left][right] = 0;
                    continue;
                }
                for (int k = left;k <= right;k++){
                    dp[left][right] = min(dp[left][right], mx + dp[left][k - 1] + dp[k + 1][right]);
                }
            }
        }
        cout << dp[1][m] << endl;
    }
    
    return 0;
}