[BZOJ1571][Usaco2009 Open]滑雪课Ski

比较水的动规。

注意到这题主要的变量就是时间和能力值，而且时间能力值<=10000100，因此空间上能够承受二维的状态。

用f[i, j]表示在第i时刻，能力值为j的情况下，所能滑的最大距离。

每一天最多有三种事情可以做：喝果汁、滑雪，有时还可以上课。
  1. 如果喝果汁的话，那么可以直接从f[i, j]转移到f[i+1, j]
  2. 如果滑雪的话，显然我们要滑当前能力值能滑的最短的雪道，因为越短所需的时间越少，而且就算有零星的时间没法用到，也可以通过喝果汁解决。转移方法：f[i, j]+1转移到f[i+pre[j], j]，其中pre[j]为能力值j能滑的雪道中最短的长度。
  3. 如果当前这个时刻有一门课程的话，那么我们得考虑学习是否更优。注意：同一个时刻可能有多门课程！转移方法：f[i, j]转移到f[i+L[k], A[k]]，其中L[k]、A[k]分别为当天某个课程的学习时间和能力值

怎么计算pre[j]呢？

主程序的复杂度达到了O(t(s+100))，那么预处理采用O(n100)的朴素做法也未尝不可。当然也可以双关键字排序+线性扫描，快不了多少，而且写起来麻烦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

struct Road { int d, c; } r[10001];
struct Lesson
{
  int l, a;
  Lesson(const int x, const int y): l(x), a(y) { }
};
int t, s, n, pre[101], f[10001][101];
std::vector<Lesson> v[10001];
int main()
{
  scanf("%d%d%d", &t, &s, &n);
  for (int i = 0, m, l, a; i < s; ++i)
  {
    scanf("%d%d%d", &m, &l, &a);
    v[m].push_back(Lesson(l, a));
  }
  for (int i = 0; i < n; ++i)
    scanf("%d%d", &r[i].c, &r[i].d);
  pre[0] = 0x3FFFFFFF;
  for (int i = 1; i <= 100; ++i)
  {
    pre[i] = pre[i-1];
    for (int j = 0; j < n; ++j)
      if (r[j].c <= i && r[j].d < pre[i])
        pre[i] = r[j].d;
  }

  memset(f, 193, sizeof(f));
  f[0][1] = 0;
  for (int i = 0; i < t; ++i)
    for (int j = 1; j <= 100; ++j)
    {
      f[i+1][j] = std::max(f[i+1][j], f[i][j]);
      if (i+pre[j] <= t)
        f[i+pre[j]][j] = std::max(f[i+pre[j]][j], f[i][j]+1);
      for (std::vector<Lesson>::iterator iter = v[i].begin(); iter != v[i].end(); ++iter)
        if (i+iter->l <= t)
          f[i+iter->l][iter->a] = std::max(f[i+iter->l][iter->a], f[i][j]);
    }
  printf("%d", *std::max_element(f[t], f[t]+101));
}

Comments