furan. Imperishable Night

furan. Imperishable Night

ZOJ3375. TH08 東方永夜抄 ~ Imperishable Night

downloadsource code (ZOJ3375.cpp) [动态规划(DP), 贪心(greedy)]

这是vout同学在Contest 12 by BoMb贡献的一道题,原题是Brave Youmu,啊,妖梦同学的戏份太多了啊,于是我果断改成了二小姐挂成月赛。正如题目标题,这题是以东方永夜抄为背景的,而永夜抄得分的关键就是夜点、刻符和蓝点。当然永夜抄里是大小姐和女仆长组成红魔组解决了异变,不过这里把出场机会让给了最终鬼畜妹蓝蓝路二小姐~

  • 悪魔の妹/フランドール・スカーレット(Flandre Scarlet 芙兰朵露·斯卡雷特)
  • 永遠に紅い幼き月/レミリア・スカーレット(Remilia Scarlet 蕾米莉亚·斯卡雷特)

芙兰要在迷途竹林n个部分分别收集ITEM和TIME两种道具以获得尽量高的分数。有两个值IV和TV,在第i部分,如果在某个时刻收集了一个ITEM,那么得分增加IV,同时TV增加a[i];如果收集一个TIME,那么得分增加TV,同时IV增加b[i]。第i部分有x[i]个ITEM和y[i]个TIME。离开某个部分后,IV和TV值都会保留不变。现在的问题是,如何安排进入每个部分的顺序,以及每个部分里收集ITEM和TIME的顺序,使得最后能得到的总分最高。

下面贴作者自己的解题报告。

首先,对于每个part,设如果在IV和TV在这个part中初始都为0时,在这个part中能收集到的最大的能量为gao[i]。再设进入这个part之前的IV值和TV值分别为IV0和TV0,那么在这个part中实际能得到的最大能量为IV0 * x[i] + TV0 * y[i] + gao[i]。而每个part进行完后,IV和TV肯定是分别增加了b[i] * y[i]和a[i] * x[i],也就是说在只要知道在进入这个part之前,已经完成了哪些part,连顺序都不用考虑,就可以知道IV0和TV0的值。因为n≤15,可以使用状态压缩的DP来求解。

再考虑如何算出gao[i]。可以用dp的方法,设dp[x][y]为收集了x个ITEM和y个TIME能得到的最大能量。那么就有dp[x][y] = max(dp[x - 1][y] + b[i] * y, dp[x][y - 1] + a[i] * x)。于是有gao[i] = dp[x[i]][y[i]],这个时间复杂度为x[i] * y[i]。

事实上直接贪心即可!不妨设某个part中a[i] > b[i],那么收集方法应该是先把所有的ITEM收集,再把所有的TIME收集。反之亦然。证明如下:设一个收集序列为*****TI*****,T代表收集了TIME,I代表收集了ITEM,那么通过交换相邻的T和I的,一定可以使得到能量增加。设收集这个T之前,IV和TV分别为IV1和TV1,那么按照TI的顺序,得到的能量为TV1 + (IV1 + b[i]),收集完这两个后,IV = IV1 + b[i], TV = TV1 + a[i]。如果按照IT的顺序,收集完这两个后,IV = IV1 + b[i], TV = TV1 + a[i]是一样的,但是得到的能量就是IV1 + (TV1 + a[i]),比TI更多。因此,凡是遇到TI,就变为IT,这样一来,最优的顺序肯定是IIIII……TTTTT。于是有gao[i] = max(a[i], b[i]) * x[i] * y[i],这个时间复杂度是O(1)的。





©2010 Zhejiang University ACM/ICPC Team
©2010 http://watashi.ws/acm_x_touhou/

2 Responses to “furan. Imperishable Night”
  1. lisongs1 says:

    额,开到dp[2^15+10]也ac,可能是边界问题没处理好…

  2. lisongs1 says:

    请问:n<=15,为什么开dp[2^16] ac,dp[2^15]就wa呢?

  3.  
Leave a Reply