题面解释:

在一个基站链式组网中，有 $N$ 个基站，按照从左到右的顺序编号。现有多个“业务”需求，每个业务用三元组表示：起始基站编号、结束基站编号和利润。基站只能被一个业务占用，所选业务集合必须保证没有基站重复使用。目标是选择一组业务，使得总利润最大化。输入包含两个整数 $N$（基站数量，范围 $[1, 10000]$）和 $M$（业务数量，范围 $[1, 100000]$），接下来是 $M$ 行，每行三个整数 $K1$、$K2$ 和 $R$，表示起始基站编号、结束基站编号和利润，其中 $K1, K2 < N$ 且 $K1 < K2$，利润 $R$ 的范围为 $[1, 100]$。输出一个整数，表示能够获得的最大利润。

思路：动态规划

本题为LeetCode原题:1235. 规划兼职工作的化简版

对于处于位置$K2$处的一个可选基站，其占据位置为$[K1,K2]$，利润为$R$。那么如果要选择该基站，上一个基站必须处于$K2$之前。

定义$f[i]$表示终点在$i$及以前的所有基站所能获得的最大利润，有：

$f[i]=max\{f[i-1],f[K1_j-1]+R_j\}$。

其中$K2_j==i$。

动态规划思路

我们定义一个动态规划数组 $f[i]$，表示以基站 $i$ 为终点的所有业务所能获得的最大利润。根据题意，状态转移方程可以表示为：

其中 $K2_j == i$，即终点为 $i$ 的所有业务，$K1_j$ 是该业务的起始基站编号，$R_j$ 是该业务的利润。这个公式的含义是，我们在计算基站 $i$ 的最大利润时，有两个选择：要么不选择终点为 $i$ 的业务，这样利润就是 $f[i-1]$；要么选择终点为 $i$ 的某个业务，这时我们需要查看其起始位置的最大利润（即 $f[K1_j-1]$）加上当前业务的利润 $R_j$。

实现步骤

1. 输入处理：

   • 首先读取基站数量 $N$ 和业务数量 $M$。
   • 使用一个数组 a 来存储每个基站终点为 $i$ 的所有业务信息，包括起始位置和利润。

2. 动态规划计算：

   • 初始化动态规划数组 $f$，对于每个基站 $i$，初始值为 $f[i-1]$，表示不选择任何终点为 $i$ 的业务。
   • 遍历所有终点为 $i$ 的业务，更新最大利润值。
   • 通过 max 函数更新 $f[i]$ 的值。

3. 输出结果：

   • 最终，$f[n]$ 就是以第 $N$ 个基站为终点的所有业务所能获得的最大利润。

代码

C++

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

const int maxn=1e4+10;  // 定义最大可处理的基站数量
int n, m;  // n表示最大基站位置，m表示基站数量
vector<pair<int, int>> a[maxn];  // 用于存储每个终点位置的基站信息 (起点, 利润)
int f[maxn];  // 动态规划数组，存储终点为i的最大利润

int main() {
    cin >> n >> m;  // 输入n和m
    for (int i = 1; i <= m; ++i) {
        int l, r, c;  // l为基站起点，r为终点，c为利润
        cin >> l >> r >> c;  // 输入基站信息
        a[r].push_back(make_pair(l, c));  // 按照终点r将基站信息存入a[r]
    }
    
    // 动态规划计算
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1];  // 不选择终点为i的基站，继承f[i-1]
        for (auto x : a[i]) {  // 遍历所有终点为i的基站
            f[i] = max(f[i], f[x.first - 1] + x.second);  // 更新最大利润
        }
    }
    
    cout << f[n];  // 输出n位置的最大利润
    return 0;
}

python

n = int(input())  # 输入n，表示最大基站位置
m = int(input())  # 输入m，表示基站数量
arr = [list(map(int, input().split())) for _ in range(m)]  # 输入每个基站的起点、终点和利润
arr.sort(key=lambda x: x[1])  # 按照基站的终点位置排序
g = [-1] * (n + 1)  # 动态规划数组，初始化为-1，表示未计算状态
g[0] = 0  # 基础状态，终点为0时，利润为0
now = 0  # 当前处理到的基站索引

# 动态规划计算
for i in range(1, n + 1):
    g[i] = g[i - 1]  # 不选择终点为i的基站，继承g[i-1]
    while now < m and arr[now][1] == i:  # 遍历所有终点为i的基站
        x, y, v = arr[now]  # 读取基站的起点x，终点y，利润v
        now += 1  # 处理下一个基站
        g[y] = max(g[y], g[x - 1] + v)  # 更新最大利润

print(g[n])  # 输出n位置的最大利润

java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 输入最大基站位置n
        int m = sc.nextInt(); // 输入基站数量m
        
        int[][] arr = new int[m][3]; // 用于存储每个基站的起点、终点和利润
        
        // 读取基站信息
        for (int i = 0; i < m; i++) {
            arr[i][0] = sc.nextInt(); // 读取基站的起点
            arr[i][1] = sc.nextInt(); // 读取基站的终点
            arr[i][2] = sc.nextInt(); // 读取基站的利润
        }
        
        // 按照终点对基站进行排序
        Arrays.sort(arr, (a, b) -> Integer.compare(a[1], b[1]));
        
        int[] g = new int[n + 1]; // 动态规划数组，存储到达每个位置的最大利润
        Arrays.fill(g, -1); // 初始化为-1，表示未处理的状态
        g[0] = 0; // 基础状态，终点为0时，利润为0

        int now = 0; // 当前处理的基站索引
        // 动态规划计算
        for (int i = 1; i <= n; i++) {
            g[i] = g[i - 1]; // 不选择终点为i的基站，继承g[i-1]
            while (now < m && arr[now][1] == i) { // 遍历所有终点为i的基站
                int x = arr[now][0]; // 基站起点
                int y = arr[now][1]; // 基站终点
                int v = arr[now][2]; // 基站利润
                now++; // 处理下一个基站
                g[y] = Math.max(g[y], g[x - 1] + v); // 更新最大利润
            }
        }
        
        System.out.println(g[n]); // 输出n位置的最大利润
        sc.close();
    }
}

题目内容

有$N$个基站采用链式组网，按照从左到右编码为$1$到$N$编号。

已知定义“业务”概念为三元组(基站起始编号，基站结束编号，利润)，意味着需要占据基站起始编号到基站结束

编号的所有基站，打通信号流，可以获得对应利润。

现在外部存在多个“业务"需求待接纳，但基站使用具有排他性，也就是说一旦某一个业务占据某个基站，其他

业务不可以再使用此基站。

那么接纳哪些业务需求，可以使得利润最大化?

输入描述

第一行，输入$N$，表示有$N$个基站。$N$取值范围$[1,10000]$

第二行，输入$M$，表示有$M$组业务。,M取值范围$[1,100000]$

接下来$M$行：每行输入三个整数$K1$ $K2$ $R$，以空格隔开，表示起始基站编号，结束基站编号，利润。$K1，K2＜N，K1＜K2$，$R$取值范围$[1,100]$

输出描述

输出只有一个整数，表示获取的利润

样例1

输入

5
2
1 5 4
2 4 8

输出

8

说明

样例2

输入

5
2
1 5 4
2 4 1

输出

4

说明

$1-5$已经使用过，$2$到$4$不能再使用的

样例3

输入

20
6
1 6 1
3 10 2
10 12 3
11 12 2
12 15 2
13 18 1

输出

5

说明

我们可以这么选择业务：

$3$ $10$ $2$；选择$3$到$10$的基站，获利$2$

$11$ $12$ $2$；选择$11$到$12$的基站，获利$2$

$13$ $18$ $1$；选择$13$到$18$的基站，获利$1$

最终获利$5$

也可以选择

$1$ $6$ $1$

$10$ $12$ $3$

$13$ $18$ $1$

注意使用的基站不能重合