《Legendary Items》题目分析

拿到这题第一个想法可能就是按照题目中的二叉树来求解期望任务数。这张图其实既是出题人的一个陷阱也是一个提示。它虽然直接告诉了我们一种正确的算法求解期望任务数，但是这个算法时间复杂度非常高。分析可知这棵二叉树中的节点数量是指数级O(c^N)的。这样的算法只能得到30分左右。

提示也隐藏在这张图中，我们仔细观察可以发现红圈中的子树和黄圈中的子树一模一样。

这提示我们，无论第一件传说物品是怎么获得的（完成第一件任务就获得还是完成两件任务后获得），第二件传说物品都是从25%概率开始，与第一件无关。换句话说，每件传说物品的获得都是独立的，就好像掷N枚骰子每枚骰子的点数是相互独立的一样。

我们知道如果X和Y是两个独立的随机变量，那么E(X+Y)=E(X)+E(Y)。于是我们可以分别求出获得第一件、第二件……第N件传说物品的期望任务数，再把它们加起来就是最终答案。

我们知道第i件传说物品起始的概率是⌊P/(2i-1)⌋%，为了描述方便把它记作Pi；任务失败后概率增加Q%。用二叉树表示大概是这样：

由于概率不断增加Q%，我们最多完成100个任务就一定能获得第i件传说物品。所以计算第i件传说物品的期望任务数的复杂度是O(100)。一般我们在计算复杂度时是忽略常数的，不过这里100次计算是一个比较大的常数，为了体现这一点我们姑且把这个复杂度记作O(100)。这样计算N件传说物品的总复杂度就是O(100N)的。这个算法已经相当不错了，大概能得到90/100分。

如果我们进一步分析，会发现虽然我们计算了N棵二叉树对应的期望任务数。但这N棵二叉树总共最多有101种形态。因为Q不变，Pi的值唯一决定了这棵二叉树长什么样子，而Pi一共有0~100共101种取值。所以我们只需预先求出起始概率分别是100%、99%、98% … 0%时的期望任务数，保存在数组f[]里。计算第i件传说物品时，根据Pi直接把相应的f[Pi]累加即可。

值得一提的是，我们可以用倒推的方法求出f[]，而不用每次O(100)重新计算。

f[100] = 1;
for(int i = 99; i >= 0; i--) {
    int j = min(i + Q, 100);  //计算如果这次任务没获得，下一个任务获得的概率
    //i%的概率1次获得，(1-i%)的概率是从j%起始的期望任务数+1
    f[i] = i% * 1 + (1-i%) * (f[j] + 1);
}

于是我们得到了一个O(100+N)的算法，比之前的O(100N)好了100倍。

如果我们再进一步分析，我们会发现⌊P/(2i-1)⌋%会很快下降到0。实际上从第8件传说物品开始，起始概率就一定都是0了。也就是说从第8件开始我们可以直接用f[0]*(N-7)算出期望任务数的和。这样我们得到了一个更快的O(100+8)的算法。这个算法对于每组数据只需要常数次计算即可得到答案。