[USACO09OPEN]滑雪课Ski Lessons

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[USACO09OPEN]滑雪课Ski Lessons,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目描述

Farmer John wants to take Bessie skiing in Colorado. Sadly, Bessie is not really a very good skier.ios

Bessie has learned that the ski resort is offering S (0 <= S <= 100) ski classes throughout the day. Lesson i starts at time M_i (1 <= M_i <= 10,000) and lasts for time L_i (1 <= L_i <= 10,000). After lesson i, Bessie's ski ability becomes A_i (1 <= A_i <= 100). Note: this ability is an absolute, not an incremental change.安全

Bessie has purchased a map which shows all N (1 <= N <= 10,000) ski slopes along with the time D_i (1 <= D_i <= 10,000) required to ski down slope i and the skill level C_i (1 <= C_i <= 100) required to get down the slope safely. Bessie's skill level must be greater than or equal to the skill level of the slope in order for her to ski down it.less

Bessie can devote her time to skiing, taking lessons, or sipping hot cocoa but must leave the ski resort by time T (1 <= T <= 10,000), and that means she must complete the descent of her last slope without exceeding that time limit.ide

Find the maximum number of runs Bessie can complete within the time limit. She starts the day at skill level 1.ui

Extra feedback will be provided on the first 50 submissions.this

Farmer John 想要带着 Bessie 一块儿在科罗拉多州一块儿滑雪。很不幸,Bessie滑雪技术并不精湛。 Bessie了解到,在滑雪场里,天天会提供S(0<=S<=100)门滑雪课。第i节课始于M_i(1<=M_i<=10000),上的时间为L_i(1<=L_i<=10000)。spa

上完第i节课后,Bessie的滑雪能力会变成A_i(1<=A_i<=100). 注意:这个能力是绝对的,不是能力的增加值。three

Bessie买了一张地图,地图上显示了N(1 <= N <= 10,000)个可供滑雪的斜坡,从第i个斜坡的顶端滑至底部所需的时长D_i(1<=D_i<=10000),以及每一个斜坡所须要的滑雪能力C_i(1<=C_i<=100),以保证滑雪的安全性。Bessie的能力必须大于等于这个等级,以使得她可以安全滑下。ip

Bessie能够用她的时间来滑雪,上课,或者美美地喝上一杯可可汁,可是她必须在T(1<=T<=10000)时刻离开滑雪场。这意味着她必须在T时刻以前完成最后一次滑雪。 求Bessie在实现内最多能够完成多少次滑雪。这一天开始的时候,她的滑雪能力为1.ci

输入输出格式

输入格式:
  • Line 1: Three space-separated integers: T, S, and N

  • Lines 2..S+1: Line i+1 describes ski lesson i with three

space-separated integers: M_i, L_i, and A_i

  • Lines S+2..S+N+1: Line S+i+1 describes ski slope i with two

space-separated integers: C_i and D_i.

输出格式:

A single integer on a line by itself, the maximum number of runs that Bessie may ski within the time limit.

输入输出样例

输入样例#1:
10 1 2 
3 2 5 
4 1 
1 3 
输出样例#1:
6 

说明

Ski the second slope once, take the lesson, and ski the first slope 5 times before time is up: a total of 6 slopes.

首先分析数据范围,显然不能和时间和斜坡扯上关系

那么咱们能够构想以课程为状态的dp方程

由于两个课程之间确定是尽量选择耗时最小的做业

首先贪心求出能力为i时,作1份做业须要的最短期c[i],而后dp

令f[i]为第i课程开始时的最大做业数

f[i]=max(f[j]+(class[i].t-class[j].t-class[j].s)/(c[class[j].c]))

这一题要注意细节,好比课程之间的间隙

还有初始值和T时刻,两个均可以看成课程,但初始课程的t为1(仔细想一想)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 struct Messi
 7 {
 8     int m,l,a;
 9 }a[201];
10 int t,s,n,c[10001],d[10001],ss,f[201];
11 bool cmp(Messi a,Messi b)
12 {
13     return (a.m<b.m||(a.m==b.m&&a.l<b.l));
14 }
15 int first[101];
16 int main()
17 {int i,j;
18 //freopen("file.in","r",stdin);
19     cin>>t>>s>>n; 
20     memset(first,127/2,sizeof(first));
21      for (i=1;i<=s;i++)
22      {
23          scanf("%d%d%d",&a[i].m,&a[i].l,&a[i].a);
24      }
25      a[s+2].a=1;a[s+1].m=t;a[s+1].l=0;a[s+1].a=0;
26       for (i=1;i<=n;i++)
27       {
28           scanf("%d%d",&c[i],&d[i]);
29           first[c[i]]=min(first[c[i]],d[i]);
30       } 
31       for (i=1;i<=100;i++)
32        first[i]=min(first[i],first[i-1]);
33       sort(a+1,a+s+3,cmp);
34        for (i=2;i<=s+2;i++)
35        {
36             for (j=1;j<=i-1;j++)
37              {
38                  int d=a[i].m-a[j].m-a[j].l;
39                  if (d)
40                  f[i]=max(f[i],f[j]+d/first[a[j].a]);
41           }
42        }
43        cout<<f[s+2];
44 }