「洛谷P2948」滑雪课 题解

题目

思路

1. 首先将所有课程按结束时间排序
2. 将相同滑坡能力值的分为一类, 对于能力为\(i\)的取其中所需时间最短的\(lastmin_i\)
3. \(f(i, j)\)表示对于第\(i\)个时刻, 能力值为\(j\)或\(j\)以上时最大的滑雪次数
4. 若第\(j\)个课程开始于\(begin\)结束于\(i\), 若参加这个课程, 枚举开始时的能力值\(k, f(i, abi_j)=max\{f(begin, k) | k<=100\}\) (\(abi_j\)是第\(j\)次获得的滑雪能力), 再枚举\(abi_j\)以下的能力\(k, f(i, k)=max\{f(i, k), f(i, j)\}\)
5. 对于每一个时刻\(i\), 若滑雪, 枚举滑雪时的能力值\(k, f(i, k)=max\{f(i-lastmin_k, k)|k<=100, i-lastmin_k>=0\}\)

代码

注: 以下代码已省略头文件、read和write

class Class {
public:
  int begin, end, abi;
}c[M];
// 课程类型, 可以视作struct
int dp[N][M];
int lastmin[M];
int main () {
  int n, m, t;
  read(t);
  read(n);
  read(m);
  for (int i = 1; i <= n; i++) {
    int begin, last, abi;
    read(begin);
    read(last);
    read(abi);
    c[i].begin = begin;
    c[i].end = begin + last;
    c[i].abi = abi;
  }
  std::sort(c + 1, c + n + 1, [](Class i, Class j) {
    return i.end < j.end;
  });// 给课程按结束时间排序, 用到了匿名(lambda)函数, 需要开C++11
  for (int i = 1; i <= 100; i++) {
    lastmin[i] = inf;
  }
  for (int i = 1; i <= m; i++) {
    int need, last;
    read(need);
    read(last);
    lastmin[need] = std::min(lastmin[need], last);
  }
  memset(dp, -1, sizeof(dp));
  for (int i = 0; i <= t; i++) {
    dp[i][1] = 0;
  }
  int ans = 0;
  for (int i = 1, j = 1; i <= t; i++) {// j表示下一个课程的编号
    if (c[j].end == i) {
      for (int k = 1; k <= 100; k++) {
        dp[i][c[j].abi] = std::max(dp[i][c[j].abi], dp[c[j].begin][k]);
      }
      for (int k = 1; k < c[j].abi; k++) {
        dp[i][k] = std::max(dp[i][k], dp[i][c[j].abi]);
      }
      j++;
    }// 上课
    for (int k = 1; k <= 100; k++) {
      if (i - lastmin[k] >= 0) {
        if (dp[i - lastmin[k]][k] != -1) {
          dp[i][k] = std::max(dp[i][k], dp[i - lastmin[k]][k] + 1);
          ans = std::max(ans, dp[i][k]);
        }
      }
    }// 滑雪
  }
  write(ans), putchar('\n');
  return 0;
}