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 ;
}