yuyuko. Hanami Party

yuyuko. Hanami Party

ZOJ3385. 花見(flower viewing, 赏花会)

downloadsource code (ZOJ3385.cpp) [贪心(greedy)]

这道题是贪心帝猛犸也钻地在集训Contest 11 by ACFun时沿着我的水题youmu. Yuyuko and Youmu所出的神题。虽然标程去掉assert只有25行,但当时无人AC(掉到别的坑里也是一个原因吧)。

  • 幽冥楼閣の亡霊少女/華胥の亡霊/西行寺幽々子(さいぎょうじ ゆゆこ)
  • 幽人の庭師/半分幻の庭師/半人半霊の半人前/魂魄妖夢(こんぱく ようむ)

UU子要在N天后举办赏花会,而准备赏花会食物的任务交给了妖梦,可是UU子是个贪吃鬼,在第i天需要吃掉a[i]的食物。起初,妖梦的厨艺等级为L,意味着一天可以准备L单位的食物。在每一天,妖梦可以选择如下行为中的一种:

  • 使用幻想御手(Level Upper)提升厨艺等级L
  • 准备L单位的食物。

为了圆满举办赏花会,妖梦要在满足UU子每天食物消耗的前提下,准备尽量多。假设初始没有食物剩余,赏花会上最多能准备好多少食物?

作者原本在寻找一个O(nlgn)的算法,后来果断找到了O(n)的贪心 orz 首先会想到应该尽量早的升级,不得以才放弃升级,改成准备食物,当然最后几天可能都准备食物比较好。于是有下面的伪代码

用一个堆栈s记录用于升级的天数
foreach i = 1 to n
	假设第i天用于升级,把i压入栈中
	while 食物准备量 小于 UU子前i天所需食物的部分和
		调整:把最后一次的升级改成准备食物,即抛出栈顶元素j
		更新食物准备量,这可以O(1)实现
	if 调整失败
		Myon
while 把最后一次升级改成准备食物可以准备更多的食物
	调整并更新食物准备量

附上作者对算法简单的论证:

  1. 默认地将提升L的策略放入决策队列中(贪心:提升L的决策越靠前越好),因此只有通过去除队列中的L才能增加总食物数(将提升L转变为make food);
  2. 记在第k1,k2,..km天采用了提升L的策略,如果要去除其中确定的几天,显然去除顺序是没有影响的;
  3. 既然去除顺序无关,就可以贪心地选择增益效果最大的那天,也就是k1,k2,…,km最靠后的一天(显然);
  4. 记当前天为 i,去除决策L的那天为k,只要对于当前天而言,食物变化△>0,那么就不会影响到k~i-1天之内的正确性(线段右端点升高,但斜率降低,因此从右端点向左,提升幅度会更大);
  5. 只有在当前食物不足或最后一天时才将之前的决策L转换为make food(保证后续天里的L尽可能地高)。





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

11 Responses to “yuyuko. Hanami Party”
  1. CrazyCow says:

    笑而不语。

  2. CrazyCow says:

    标程好像有问题的,
    9 2
    1 2 3 1 1 5 1 1 1

    ps:留言有时怎么留不上呀?服务器问题?

    • 猛犸也钻地 says:

      1 2 3 1 1 5 <- 这里1 1 5需要7个,中间只能不停制造食物断不了,于是只能Myon了,标程输出无误

  3. 游客 says:

    测试下留言板

  4. CrazyCow says:

    标程ms有问题 见:
    9 2
    1 2 3 1 1 5 1 1 1
    应该是“Myon”吧.

    • watashi says:

      可能是ipv6地址段有机器人的原因,你的留言被akismet判定为灌水了
      确实我的程序错了…… :oops:
      应该在中间每次都要判断cur < sum的,我修改了一下……看来数据有点弱,我去update一下,谢谢指出

  5. cgy4ever says:

    这道题和curimit神牛的集训队论文题几乎一样,只是他那道数据更大些。
    原来这个数据量下竟然有如此简洁的算法,赞啊!

  6.  
Leave a Reply