题解 P4550 【收集邮票】
command_block
2018-12-29 23:35:39
深夜肝题纪念。
期望题道道都是神题,蒟蒻表示Orz。
~~感觉我的思路没有那么麻烦。~~
这道题题目描述有点模糊,并不是买第$i$种邮票需要$i$元,而是第$i$次买邮票需要$i$元。
假如皮皮花了x步收集了全部的邮票,那么花费就是$1+2+3+...+x=x(x+1)/2$(等差数列)。
化简得$(x^2+x)/2$。
我们就是要求$(x^2+x)/2$的期望。
**平方的期望不等于期望的平方。**
由于期望的线性性,可以转化为分别维护**平方的期望**与**线性期望**。
这种套路题都是要**倒推**。
设$p1[i]$为收集了$i$张邮票之后还要花费的次数的期望。$p2[i]$为收集了$i$张邮票之后还要花费的次数**平方**的期望。
易得$p1[n]=p2[n]=0$(都拿到了之后就不用收集了)
答案就是$(p2[0]+p1[0])/2$
转移:
$\Large{1.p1}$
$p1[i]=(i/n)(p1[i]+1)+(n-i)/n(p1[i+1]+1)$
这个好理解,有(i/n)的概率买到已有的,这时候花费**变**为(p1[i]+1);
有(n-i)/n的概率买到没有的,这时候花费**变**为(p1[i+1]+1);
像解一元一次含参方程一样:
$p1[i]=(i/n)(p1[i]+1)+(n-i)/n(p1[i+1]+1)$
$p1[i]=(i/n)p1[i]+(n-i)/n*p1[i+1]+1$
$(n-i)/n*p1[i]=(n-i)/n*p1[i+1]+1$
$p1[i]=p1[i+1]+n/(n-i)$
$\Large{1.p2}$
开始麻烦了。
想了解更多非线性期望套路,见[P1654 OSU!](https://www.luogu.org/problemnew/show/P1654)一题。
$p2[i]=i/n*(p2[i]+2*p1[i]+1)+(n-i)/n*(p2[i+1]+2*p1[i+1]+1)$
老样子,有(i/n)的概率买到已有的,有(n-i)/n的概率买到没有的。
前者花费**变**为(花费的次数+1)的平方的期望,因为$E((x+1)^2)=E(x^2)+2E(x)+1$,所以得$(p2[i]+2*p1[i]+1)$
同理后者花费**变**为$(p2[i+1]+2*p1[i+1]+1)$
理解了上面的式子,下面就是套路化简。
$p2[i]=i/n*(p2[i]+2*p1[i]+1)+(n-i)/n*(p2[i+1]+2*p1[i+1]+1)$
$p2[i]=i/n*p2[i]+i/n*(2*p1[i]+1)+(n-i)/n*(p2[i+1]+2*p1[i+1]+1)$
$(n-i)/n*p2[i]=i/n*(2*p1[i]+1)+(n-i)/n*(p2[i+1]+2*p1[i+1]+1)$
$p2[i]=i/(n-i)*(2*p1[i]+1)+p2[i+1]+2*p1[i+1]+1$
推完了式子之后,代码就很简单了。
Code:
```cpp
#include<cstdio>
using namespace std;
int n;
double p2[10500],p1[10500];
int main()
{
scanf("%d",&n);
p2[n]=0;p1[n]=0;
for (int i=n-1;i>-1;i--){
p1[i]=p1[i+1]+1.00*n/(n-i);
p2[i]=1.00*i/(n-i)*(2*p1[i]+1)+p2[i+1]+2*p1[i+1]+1;
}printf("%.2lf",(p1[0]+p2[0])/2);
return 0;
}
```