E. Ski Lessons (DP)
题意:
滑雪场有N(N<=10000)种项目, 可以从任意时刻开始, 可以反复参加. 每种项目要求参与者技能值(<=100)至少为c[i], 耗费连续的d[i]单位时间.
此外,滑雪场提供S(S<=100)个培训课程. 每个课程开始时间为m[i], 持续时间l[i], 结束后, 参加者的技能值变为a[i]. 如果选择参加某个课程,不能迟到早退. 只能同时参加一个课程.
一个人在任意时刻只能做一件事, 而且他总共有 T(T<=10000) 单位时间. 他必须在时刻T结束所有活动.
问如何安排可以使得此人参加最多次滑雪项目, 求最大次数.
解:
O(100*N)预处理, len[i][j]表示技能值为i时, 参加一次任意项目的最短时间.
O(S*S)DP, dp[i]表示在课程i开始的前一时刻, 已参加项目的最大次数.
注意到, 结束一项课程后人的技能值是一定的. 因此, 可以枚举参加i之前最近参加的课程k, 两次课程之间的收益可直接计算. 则dp[i] = max(dp[k]+ (m[i]-m[k]-l[k])/len[a[k]]).
posted on 2009-06-29 22:11
wolf5x 阅读(125)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc