剑与魔法-解题报告

剑与魔法-解题报告

标签(空格分隔): 编程 解题报告


1.题面

剑与魔法
时间限制: 1 Sec 内存限制: 128 MB

题目描述
万老师听说某大国很流行穿越,于是他就想写一个关于穿越的剧本。
闲话休提。话说老师穿越到了某一个剑与魔法的大陆。因为如此这般,所以老师从维娜艾那里得到了预言。老师一共被告知了若干件按顺序结算的事件。这些事件分为两类:战役事件(CASE)、穿越回去事件(END)。战役事件可以选择是否参加,参加了之后会获得一定的金钱。每个END事件发生需要至少参加一定数量的战役事件。特别的是,END事件如果满足要求就会强制发生。老师希望在大陆玩个够,所以他要求只有最后一个END事件会发生。老师希望获得最多的金钱,所以求助于你。

输入
第一行一个数N,表示输入文件有多少行。
接下来每一行用空格隔开一个字符和一个整数。字符为“c”表示战役事件,接下来的整数表示这次涨RP顺带有多少钱;字符为“e”表示穿越回去事件,接下来的整数代表至少要涨多少RP。最后一个事件保证是END事件。

输出
第一行一个整数,最多金钱数目。
若不可能则输出-1。

样例输入

样例输出

提示
【数据说明】
30%的数据满足 N<=20
60%的数据满足 N<=1,000
100%的数据满足 N<=200,000
每次涨RP事件赏金不超过10,000
穿越事件的要求不超过200,000

2. 心路历程

这道题的第一感觉是DP,然后经过设计,发现这是一个2D/0D的动态规划,虽然空间可以用滚动数组的方式优化到一维,但是时间方面很难再去优化(?是否有方式可以优化此类DP?)。然后我就只得到了60分。
这道题的正解是贪心,构建一个小根堆。代码见第4节。
其实考试的时候我是想到过贪心的,当时也设计出了一个错误的贪心,证明它错误后就放弃了贪心算法。表面上是因为逻辑不够紧密,不能因为一个错误的算法就排除一类算法;其实是因为我看到题目的第一感觉就觉得贪心不怎么靠谱,要用DP;最终是主观臆想影响了我的逻辑过程。
综上,在进行算法设计的时候,可以有第一感觉,但不能因为第一感觉而影响了自己的逻辑思考;算法不能倾注过多的感性认识。

3. 各种各样的算法

30% N<=20

应该是暴搜吧,具体我也没有想过

60% N<=1,000

数据是为DP准备的,正如我在第2节中说的,这是一个2D/0D的DP,后续应该是有优化的可能的,但是我不会。如果有哪位大神愿意教教我,可以给我留言哈。下面给出DP的状态、转移及初值、终值。

f[i][j]表示到第i行,参加了j场战役的最大金币数
f[i][j]=max(f[i-1][j],f[i-1][j-1]+val[i]) (ch[i]=='c')
f[i][j]=f[i-1,j] (j&lt;=val[i]-1)
初值:f[0][0]=0; f[i][j]=-1; (i0 || j0)
终值:Max{ f[n][i] } (i>=val[n])

DP的正确性可以用最优子结构和重叠子问题(无后效性)来验证。

100% N<=200,000

正解是贪心,用优先队列(小根堆)来维护局部最优。
具体来讲,可以把每一个“END”时间看做一个限制,限制了什么呢?除了最后一个END意外,其余都限制了到当前位置,可以参加的战役数的最大值。所以,具体步骤大概是这样的:

我们不妨来证明一下这个贪心的正确性。
这个贪心的正确性,是由循环不变式决定的:在每个循环操作完成后(即2或3执行完,4执行前时),截止当前,不是小根堆中的元素必然不会存在于答案之中,答案肯定存在于小根堆中

聪明的你是否已经发现,这里其实有2个命题,我们先粗略证明
第一个:
如果这个元素不在小根堆中,因为只有步骤3会弹出元素,所以其肯定是在步骤3中被弹出的。
也就是说,在其被弹出时,它是小根堆中较小的(heap.size-(val-1))个元素(这里的heap.size是指本次操作3开始前的状态)。因为必须要满足小根堆中只能有(val-1)个元素,所以这个元素肯定不在最终的答案里。
第二个:
因为所有可能是答案的值都被压入过堆(由步骤2,所有元素不管如何,都会被压进小根堆),所以答案一定在堆中。

接下来是详细的证明:

初始化:此时,小根堆中要么只有一个元素(第一个是CASE事件),要么没有元素(第一个是END事件)。显然,两个命题都成立。
保持:由前面的粗略证明可知。
终止:最后一步执行完,也符合粗略证明。

证毕。
(本人第一次正儿八经地证明,如果有错误,欢迎大神指出!)

4. AC代码(Pascal)

相关文章

2 条评论
  1. Pascal手写的大佬%%%
    我只能用priority_queue了。

  2. Thanks for every one of your effort on this web page. Kate really likes conducting investigations and it’s really simple to grasp why. My partner and i know all regarding the compelling ways you give invaluable tips by means of this blog and cause participation from people on this concept and our princess is really starting to learn a lot of things. Take pleasure in the remaining portion of the new year. Your performing a wonderful job.

发表一条评论