reimu. Osaisen Choudai!

reimu. Osaisen Choudai!

ZOJ3381. お賽銭♥ちょうだい(Donations♥Please お賽銭頂戴!)

downloadsource code (ZOJ3381.cpp) [动态规划(DP), 线段树(SegmentTree)]

题目名称「お賽銭♥ちょうだい」是miko在「東方河想狗蒼池」中的一首東方アレンジ(略鬼畜電波/原曲Dream Battle)。怎么说呢,题目的背景倒是很符合这首歌的歌词和红白“无节操”的称号,不过不知道投入10w会发生什么呢(笑)。顺便补充一下,题目中gif动画的配图捏的是《少女爱上姐姐》的ED,不知道有多少人看出来了~

osaisen-choudai-reimu

  • 夢と伝統を保守する巫女/永遠の巫女/楽園の素敵な巫女/博麗霊夢(はくれい れいむ)

无节操在第i天可以向博丽神社的访客索要s[i]的赛钱,但这样她在x[i]天内都不能再次索要,而在y[i]天内必须再次索要。显然无节操希望能够获得最多的钱,假设无节操在第一天索要了赛钱,那么她最多可以获得多少赛钱?

当然去掉在第一天索要了赛钱的限制算法还是一样的。首先很容易想到O(n^2)的动态规划算法,记dp[i]为第i天索要了赛钱的最大收益,那么dp[i] = s[i] + max{dp[i + j] | x[i] ≤ j < y[i]}。但是n有5w,于是利用线段树把原本O(n)的求max优化成O(lgn),得到一个O(nlgn)的算法。这个线段数只要实现对点更新max和对区间查询max的操作,是最简单的线段树了。这种结合并没有什么新的地方,我当时出在新手上路里,希望没见过的人了解一下。这题要比我之前出的ZOJ3227. Perfect Cherry Blossom(妖妖梦)简单得多。





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

8 Responses to “reimu. Osaisen Choudai!”
  1. Cinderella says:

    这个dp怎么是后效的呀??不是无后效性吗??不明白*_*

  2. cgy4ever says:

    这道题用spare table也可以的。

  3.  
Leave a Reply