现在的位置: 首页 > 综合 > 正文

NKPC7-2155-Crazy Review

2012年08月20日 ⁄ 综合 ⁄ 共 769字 ⁄ 字号 评论关闭

1. 概述

    题目出的很有意思,在有限的时间内,合理分配时间,得到最大的分数。标注答案是动态规划。感觉和编程之美上,一个求最大连续子数组之和的题目很像,因为两道题都涉及到了两个动态规划,而且其中的一个动态规划使用另一个动态规划。

2. 方法

    首先,判断所有课程上限是否到60分,
    然后,对于没有到60分的课程分别先学习到60分,并且更新S,V和H。
    接着,计算使用剩下的H,即时间,能够得到的最高分数。
    这里主要说一下最后一步动态规划的过程。
    SingleCourse[i][j] 表示在i号课程上,学习j小时后,能够取得的分数。
    MultiCourse[i][j] 表示在从0号课程到i号课程上,一共学习j小时候,能够取得的最大分数。
3. SingleCourse的计算

    S[i] = Min{ S[i]+V[i], U[i] } // 分数不能超过上限
    V[i] = max{ 0, V[i]+DV[i] } // 分数顶多不会增加,但是绝对不会因为复习过多而下降
    SingleCourse[i][j] = S[i]

    复杂度:    SingelCourse[20][500], T<=20*500=10000
4. MultiCourse的计算

    MultiCourse[0][j] = SingleCourse[0][j]
    对于i>0有:
    MultiCourse[i][j] = max { (SingleCourse[i][k]+MultiCourse[i-1][j-k]) } , 其中k从0到j
    复杂度: MultiCourse[20][50], T<=20*50*50=100000

5. 复杂度

    总的复杂度在10^5以内,没问题。

6. 题目网址

    http://acm.nankai.edu.cn/p2155.html

 

抱歉!评论已关闭.