题目描述
题解
我们设 f [ s ] f[s] f[s]表示选择状态为s的期望次数。
- 如果购买了新的，贡献是 f [ s 去 掉 k ] × p k f[s去掉k]\times p_k f[s去掉k]×pk?
- 如果不购买新的，概率是总数减去购买新的的概率(不能计算二进制位中0的概率，因为相加可能不等于1)，即 ∑ k ∈ s p k \sum_{k∈s} p_k ∑k∈s?pk?。
因此，我们就得到了状态转移方程：
f [ s ] = ∑ k ∈ s f [ s x o r 2 k ? 1 ] × p k + ( 1 ? ∑ k ∈ s p k ) × f [ s ] + 1 f[s]=\sum_{k∈s}f[s\ xor\ 2^{k-1} ]\times p_k+(1-\sum_{k∈s}p_k)\times f[s]+1 f[s]=k∈s∑?f[s xor 2k?1]×pk?+(1?k∈s∑?pk?)×f[s]+1
我们知道，求这种DP的方式只有高斯消元和解方程，由于只有两个未知数，我们可以选择移项：
f [ s ] = ∑ k ∈ s f [ s x o r 2 k ? 1 ] × p k + 1 1 ? ∑ k ∈ s f[s]=\frac{\sum_{k∈s}f[s\ xor\ 2^{k-1} ]\times p_k+1}{1-\sum_{k∈s}} f[s]=1?∑k∈s?∑k∈s?f[s xor 2k?1]×pk?+1?
然后就可以展示华丽丽的代码了：
#include <bits/stdc++.h>using namespace std;
const int N = 21;int n;
double p[N], f[1<<N];void work(void)
{
for (int i=1;i<=n;++i)cin>>p[i];for (int i=1;i<(1<<n);++i){
double sum = 0;f[i] = 0;for (int j=1;j<=n;++j)if ((i >> j-1) & 1) {
f[i] += f[i^(1<<j-1)]*p[j];sum += p[j];}f[i] = (f[i]+1)/sum; }printf("%.5lf\n", f[(1<<n)-1]);return;
}int main(void)
{
while (cin>>n) work();return 0;
}