|
hello
题目 754 [USACO Open09] 滑雪训练
2019-04-09 20:16:47
|
|
|
|
很好的一道动态规划。
f[i][j]为到i时刻，能力为j时的最多滑的次数，然后开三个数组来优化这个动规方程。ks[i][j]为滑雪课时间末端点为i，提到能力值为j时的始端点。我们可以贪心来确定这个值，只有这个值尽可能大才会最优。然后每次对于一次课程，要从f[ks[i][j]][任意能力值]转移过来,所以还要用g[i]表示f[ks[i][j]][任意能力值]的最大值。然后，对于能力要求值相同的滑雪坡道，贪心选择用时少的。然后就好啦  |