pache. Patchouli’s Spell Cards

pache. Patchouli’s Spell Cards

ZOJ3380. 帕秋莉的符卡

downloadsource code (ZOJ3380.java) [动态规划(DP), 组合计数(counting)]

题目最初来源于很久以前一次TC SRM 250分题目的看错题(不是第一次了)……联想帕秋莉·诺蕾姬SC的名字都是/[金木水火土日月]+符/形式的,而且数量非常多(东方很多作都是第4面不同路线有不同的SC),比如题目中出现的就有:

  • 水符「プリンセスウンディネ」Princess Undine:水精公主
  • 月符「サイレントセレナ」Silent Selena:静谧的女神 (Extra里图书馆唯一一张比较稳的SC)
  • 日符「ロイヤルフレア」Royal Flare:皇家烈焰 (大自然啊)
  • 金&水符「マーキュリポイズン」Mercury Poison:水银之毒
  • 火水木金土符「贤者の石」Philosopher’s Stones:贤者之石 (只rp爆发拿过一两次)

于是帕琪顺利成章的成为了本题主人公。本来想找帕琪和五大元素的配图,虽然找到了一些,但没有满意的,于是直接用了一张绯想天里贤者之石的截图。关于概率为0时输出“姆Q”(“mukyu~”),这是帕琪的口癖,来自东方萃梦想中魔理沙线,被打败后第一句话就是“姆Q”。

  • 知識と日陰の少女/動かない大図書館/パチュリー・ノーレッジ

有m种不同的元素,每种元素都有n种不同的相位,现在假设有每种元素各一个,其相位是等概率随机的。如果几个元素的相位相同,那么帕琪就可以把它们组合发动一个符卡(Spell Card)。现在问帕琪能够发动等级不低于l,即包含l个相同相位的不同元素的附卡的概率。

这题出水了,原本应该n的范围可以非常大。不过月赛前一天才发现,于是没有改……555 好伤心啊

还是把问题转为求m个位置,每个位置是1到n的一个数,问没有l个位置数相同的方案数。我的是空间复杂度O(m^2),时间复杂度O(m^2*l)的动态规划,这个算法即使n很大也没有问题。不过题目的n和m范围都是100,所以也可以用空间复杂度O(nm),时间复杂度为O(nml)的动态规划,算法思想是一样的。后者讲起来可能清楚一些,于是介绍后者,记dp[i][j]表示用了1到i这些数字把j个位置填好了,那么就有dp[i][j]=sum{dp[i-1][j-k]*choose[m-(j-k)][k] | k≤j && k<l}。前者无论dp和求答案都要麻烦一些,有兴趣的看代码吧,就不介绍了。

特别的,如果m<l,那么就是”mukyu~”;如果l>m/2,那么答案是可以通过比较简单的组合公式直接求出。当时训练的时候,前几个提交都是只能处理这两种情况,一般的情况就WA了,后来都去搞别的坑了。





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

Leave a Reply