问题描述

题目要求我们最大化音乐厅的全年总收入。音乐厅有两个房间，每个房间每天只能举办一场音乐会。每个申请人会指定一个时间段 [i, j] 和一个出价 w，表示他们愿意支付的金额来使用一个房间。我们需要选择一些申请，使得总收入最大化，同时满足以下条件：

1. 每个申请要么完全接受，要么完全拒绝。
2. 每个房间每天只能使用一次。
3. 每场音乐会必须在整个申请期间使用同一个房间。

输入输出格式

• 输入：多组数据，每组数据以一个整数 n 开始，表示申请数量，然后是 n 行申请信息，每行包含三个整数 i、j 和 w，分别表示申请的时间段和出价。输入以单个零结束。
• 输出：对于每组数据，输出一个整数，表示最大总收入。

解题思路

1. 数据结构设计：

   • 定义一个结构体 Req 来存储每个申请的起始时间 d0、结束时间 d1 和出价 w。
   • 使用二维数组 maxws 来存储动态规划的结果，maxws[i][j] 表示在第 i 天和第 j 天分别使用两个房间时的最大收入。

2. 排序：

   • 将所有申请按照起始时间 d0 升序排序，若 d0 相同则按结束时间 d1 升序排序。这样可以方便地处理申请的先后顺序。

3. 动态规划：

   • 初始化 maxws 数组为全零。
   • 遍历每个申请，对于每个申请 (d0, d1, w)，更新 maxws 数组：
     • 如果申请的时间段 [d0, d1] 与当前的房间使用情况不冲突，则尝试将该申请加入到当前的最大收入中。
     • 更新 maxws 数组时，需要考虑以下几种情况：
       • 申请时间段 [d0, d1] 完全占用一个房间。
       • 申请时间段 [d0, d1] 与已有的申请部分重叠。
       • 申请时间段 [d0, d1] 不与任何已有申请冲突。
   • 在更新过程中，使用一个临时数组 maxws0 来保存当前状态的更新结果，避免在更新过程中相互干扰。

4. 最终结果：

   • 最终，maxws[max_d][max_d] 就是最大总收入，其中 max_d 是所有申请中最大的结束时间。

代码实现

以下是完整的代码实现，结合上述思路进行详细解释：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */
#define MAX_D (365)

/* typedef */
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef pair<long,long> pll;
typedef long long ll;

/* classes */
class Req {
public:
  int d0, d1, w;

  Req(int _d0 = 0, int _d1 = 0, int _w = 0) {
    d0 = _d0; d1 = _d1; w = _w;
  }

  bool operator <(const Req& r) const {
    if (d0 != r.d0) return d0 < r.d0;
    return d1 < r.d1;
  }
};

/* main */
int main() {
  for (;;) {
    int n;
    cin >> n;
    if (n == 0) break;

    vector<Req> reqs(n);
    int max_d = 0;

    // 读取申请信息
    for (int i = 0; i < n; i++) {
      cin >> reqs[i].d0 >> reqs[i].d1 >> reqs[i].w;
      if (max_d < reqs[i].d1) max_d = reqs[i].d1;
    }

    // 按起始时间升序排序，若起始时间相同则按结束时间升序排序
    sort(reqs.begin(), reqs.end());

    // 初始化动态规划数组
    int maxws[MAX_D + 1][MAX_D + 1], maxws0[MAX_D + 1][MAX_D + 1];
    memset(maxws, 0, sizeof(maxws));

    // 遍历每个申请
    for (int k = 0; k < n; k++) {
      int d0 = reqs[k].d0;
      int d1 = reqs[k].d1;
      int w = reqs[k].w;
      memcpy(maxws0, maxws, sizeof(maxws)); // 复制当前状态到临时数组

      // 更新动态规划数组
      for (int i = 1; i <= max_d; i++)
	for (int j = 1; j <= max_d; j++) {
	  if (i == j && i == d1) { // 申请时间段与当前房间使用情况完全冲突
	    int wi = maxws[d0 - 1][j] + w; // 尝试将申请加入到房间1
	    int wj = maxws[i][d0 - 1] + w; // 尝试将申请加入到房间2
	    if (maxws0[i][j] < wi) maxws0[i][j] = wi;
	    if (maxws0[i][j] < wj) maxws0[i][j] = wj;
	  }
	  else if (i == d1) { // 申请时间段与房间1冲突
	    int wi = maxws[d0 - 1][j] + w; // 尝试将申请加入到房间2
	    if (maxws0[i][j] < wi) maxws0[i][j] = wi;
	  }
	  else if (j == d1) { // 申请时间段与房间2冲突
	    int wj = maxws[i][d0 - 1] + w; // 尝试将申请加入到房间1
	    if (maxws0[i][j] < wj) maxws0[i][j] = wj;
	  }

	  // 选择当前状态的最大值
	  int wij0 = maxws0[i - 1][j];
	  int wij1 = maxws0[i][j - 1];
	  if (maxws0[i][j] < wij0) maxws0[i][j] = wij0;
	  if (maxws0[i][j] < wij1) maxws0[i][j] = wij1;
	}

      memcpy(maxws, maxws0, sizeof(maxws)); // 更新动态规划数组
    }

    // 输出最大总收入
    cout << maxws[max_d][max_d] << endl;
  }

  return 0;
}

代码分析

1. 时间复杂度：

   • 排序的时间复杂度为 (O(n \log n))。
   • 动态规划部分的时间复杂度为 (O(n \times \text{max_d}^2))，其中 n 是申请数量，max_d 是最大结束时间（最多为365天）。
   • 总时间复杂度为 (O(n \log n + n \times \text{max_d}^2))。

2. 空间复杂度：

   • 使用了一个大小为 ((\text{max_d} + 1) \times (\text{max_d} + 1)) 的二维数组，空间复杂度为 (O(\text{max_d}^2))。

测试用例分析

以第一组测试数据为例：

4
1 2 10
2 3 10
3 3 10
1 3 10

• 申请1：时间段 [1, 2]，出价 10。
• 申请2：时间段 [2, 3]，出价 10。
• 申请3：时间段 [3, 3]，出价 10。
• 申请4：时间段 [1, 3]，出价 10。

通过动态规划，最终的最大总收入为 30，选择的申请为：

• 申请1：房间1在 [1, 2]。
• 申请2：房间2在 [2, 3]。
• 申请3：房间1在 [3, 3]。

总结

本题通过动态规划解决了音乐厅的最大收入问题。关键在于如何设计动态规划的状态转移方程。