USACO09OPEN滑雪课SkiLessons

洛谷2948 BZOJ1571

  • 题意
    Farmer John 想要带着 Bessie 一起在科罗拉多州一起滑雪。很不幸,Bessie滑雪技术并不精湛。 Bessie了解到,在滑雪场里,每天会提供$S (0 \le S \le 100)$门滑雪课。第$i$节课始于$M_i (1 \le M_i \le 10000)$,上的时间为$L_i (1 \le L_i \le 10000)$。上完第$i$节课后,Bessie的滑雪能力会变成$A_i (1 \le A_i \le 100)$. 注意:这个能力是绝对的,不是能力的增长值。Bessie买了一张地图,地图上显示了$N (1 \le N \le 10000)$个可供滑雪的斜坡,从第$i$个斜坡的顶端滑至底部所需的时长$D_i (1 \le D_i \le 10000)$,以及每个斜坡所需要的滑雪能力$C_i (1 \le C_i \le 100)$,以保证滑雪的安全性。Bessie的能力必须大于等于这个等级,以使得她能够安全滑下。Bessie可以用她的时间来滑雪,上课,或者美美地喝上一杯可可汁,但是她必须在$T (1 \le T \le 10000)$时刻离开滑雪场。这意味着她必须在$T$时刻之前完成最后一次滑雪。 求Bessie在实现内最多可以完成多少次滑雪。这一天开始的时候,她的滑雪能力为1.
  • Solution
    • 最终目的是多滑雪,上课是为了能快的滑雪。一开始没注意,以为课是必须要上的,那就是sb题了
    • 由于滑雪是卡在课与课之间的空隙时滑的,所以可以枚举上一节学了的课程是哪一节。
    • 能力值越高滑雪的选择越多,设$f[i][j]$代表第$i$节课之后(上或没上)能力值为$j$的最大收获。
    • 不难发现,枚举一下上一节学的课就行了。
    • 状态数为$O(S \times maxC)$,转移复杂度$O(S)$。
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std ;
void Read ( int &x, char c = getchar() ) {
for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const int maxm = 105, maxn = 1e4+5, zhf = 0x3f3f3f3f ;
struct Lesson {
int st, to, v ;
friend bool operator < ( Lesson a, Lesson b ) {
return a.st < b.st ;
}
} l[maxm] ;
struct Hill {
int v, len ;
friend bool operator < ( Hill a, Hill b ) {
return a.v < b.v ;
}
} h[maxn] ;
int n, m, t, minc[maxm], f[maxm][maxm], gn[maxm] ;
//bring your brain when you are creating an array
int main() {
#ifndef ONLINE_JUDGE
freopen ( "LG2948.in", "r", stdin ) ;
freopen ( "LG2948.out", "w", stdout ) ;
#endif
int i, j, k, maxv = 1 ;
Read(t) ; Read(m) ; Read(n) ;
for ( i = 1 ; i <= m ; i ++ ) {
Read(l[i].st) ; Read(l[i].to) ; Read(l[i].v) ;
l[i].to += l[i].st-1 ;
maxv = max(maxv, l[i].v) ;
}
sort ( l+1, l+m+1 ) ;
l[0] = (Lesson){0, 0, 1} ;
l[++m] = (Lesson){t, t, 0} ;
for ( i = 1 ; i <= n ; i ++ ) {
Read(h[i].v) ;
Read(h[i].len) ;
}
sort ( h+1, h+n+1 ) ;
k = 1 ;
minc[0] = zhf ;
for ( i = 1 ; i <= maxv ; i ++ ) {
minc[i] = minc[i - 1] ;
for ( ; k <= n ; k ++ ) {
if ( h[k].v <= i ) minc[i] = min(minc[i], h[k].len) ;
else break ;
}
}
memset ( f, -zhf, sizeof f ) ;
memset ( gn , -zhf, sizeof gn ) ;
f[0][1] = 0 ;
for ( i = 1 ; i <= m ; i ++ ) {
for ( j = 0 ; j < i ; j ++ ) {
for ( k = 1 ; k <= maxv ; k ++ ) {
f[i][k] = max(f[i][k], f[j][k] + (l[i].st-l[j].st)/minc[k]) ;
if ( k == l[j].v && l[j].to < l[i].st )
f[i][k] = max(f[i][k], gn[j] + (l[i].st-l[j].to-1)/minc[k]) ;
gn[i] = max(gn[i], f[i][k]) ;
}
}
//printf ( "gn[%d] = %d\n", i, gn[i]) ;
}
/*for ( i = 1 ; i <= m ; i ++ )
for ( j = 1 ; j <= maxv ; j ++ )
printf ( "f[%d][%d]=%d\n", i, j, f[i][j] ) ;*/
printf ( "%d\n", gn[m] ) ;
return 0 ;
}