BZOJ 1571: [Usaco2009 Open]滑雪课Ski

题目地址

描述

Farmer John 想要带着Bessie一起在科罗拉多州一起滑雪。很不幸,Bessie滑雪技术并不精湛。
Bessie了解到,在滑雪场里,每天会提供$S(0 \leq S \leq 100)$门滑雪课。第$i$节课始于$M_{i}(1 \leq M_{i} \leq 10000)$,上的时间为$L_{i}(1 \leq L_{i} \leq 10000)$。上完第$i$节课后,Bessie的滑雪能力会变成$A_{i}(1 \leq A_{i} \leq 100)$。 注意:这个能力是绝对的,不是能力的增长值。
Bessie买了一张地图,地图上显示了$N(1 \leq N \leq 10,000)$个可供滑雪的斜坡,从第$i$个斜坡的顶端滑至底部所需的时长$D_{i}(1 \leq D_{i} \leq 10000)$,以及每个斜坡所需要的滑雪能力$C_{i}(1\leq C_{i} \leq 100)$,以保证滑雪的安全性。Bessie的能力必须大于等于这个等级,以使得她能够安全滑下。
Bessie可以用她的时间来滑雪,上课,或者美美地喝上一杯可可汁,但是她必须在$T(1 \leq T \leq 10000)$时刻离开滑雪场。这意味着她必须在$T$时刻之前完成最后一次滑雪。 求Bessie在实现内最多可以完成多少次滑雪。这一天开始的时候,她的滑雪能力为$1$。

分析

动态规划水题,看到的第一眼感觉和[Hnoi2017]大佬有一点像,不过相比简单多了。

定义状态:$dp[i][j]$为在$i$时刻,上第$j$堂课能够滑雪的最多次数。(也可以定义为在时刻$i$能力为$j$,能够滑雪最多的次数)
一共有$3$种转移的状态:

  1. 美美地喝上一杯可可汁,$dp[i][j] = max(dp[i][j, dp[i - 1][j]) \cdots (i \neq 0)$
  2. 上课,$dp[i + lst[j]][j] = max(dp[i + lst[j]][j], dp[i][k]) \cdots (st[j] = i, k为满足st[j] = i的可供选择的课程编号)$
  3. 滑雪,$dp[i + a[j]][j] = max(dp[i + a[j]][j], dp[i][j] + 1) \cdots (i + a[j] \leq T)$

数组$a[]$中储存的是预处理出的在同一能力下能够在最短时间完成一次滑雪的时间,这是我们贪心的出来的显而易见的结论。

然后就是各种需要注意的小细节,然后,没有了。

代码

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
//2017/6/11 20:47
//Copyright (c) 2017年 ZJYelizaveta. All rights reserved.
//BZOJ 1571 [Usaco2009 Open]滑雪课Ski
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readIn(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int INF = 0x3f3f3f3f;
const int MAX_S = 100 + 3;
const int MAX_N = 10000 + 3;
int T, S, N;
int st[MAX_S], lst[MAX_S], abt[MAX_S];//start, last, ability
int cap[MAX_N], t[MAX_N];//capacity, time
int dp[MAX_N][MAX_S], minTime[MAX_S];

int main()
{
T = readIn(), S = readIn(), N = readIn();
//printf("%d %d %d\n", T, S, N);
for(int i = 1; i <= S; ++i) st[i] = readIn(), lst[i] = readIn(), abt[i] = readIn();
//sort(abt, abt + S)
abt[0] = 1;//
memset(minTime, INF, sizeof minTime);//
for(int i = 1; i <= N; ++i){
cap[i] = readIn(), t[i] = readIn();
for(int j = 0; j <= S; ++j){
if(cap[i] <= abt[j]) minTime[j] = min(minTime[j], t[i]);
}
}

memset(dp, -INF, sizeof dp);
dp[0][0] = 0, st[0] = -1;
for(int i = 0; i <= T; ++i){
for(int j = 0; j <= S; ++j){
if(i != 0) dp[i][j] = max(dp[i][j], dp[i - 1][j]);
if(i == st[j]){
for(int k = 0; k <= S; ++k) dp[i + lst[j]][j] = max(dp[i + lst[j]][j], dp[i][k]);
}
if(i + minTime[j] <= T) dp[i + minTime[j]][j] = max(dp[i][j] + 1, dp[i + minTime[j]][j]);
}
}

int ans = 0;
for(int i = 0; i <= S; ++i) ans = max(ans, dp[T][i]);
printf("%d\n", ans);
return 0;
}
Partager