问题 A: 礼物
时间限制: 1 Sec 内存限制: 256 MB
题面
题目描述
夏川的生日就要到了。作为夏川形式上的男朋友,季堂打算给夏川买一些生 日礼物。
商店里一共有种礼物。夏川每得到一种礼物,就会获得相应喜悦值Wi(每种 礼物的喜悦值不能重复获得)。
每次,店员会按照一定的概率Pi(或者不拿出礼物),将第i种礼物拿出来。 季堂每次都会将店员拿出来的礼物买下来。没有拿出来视为什么都没有买到,也 算一次购买。
众所周知,白毛切开都是黑的。所以季堂希望最后夏川的喜悦值尽可能地高。
求夏川最后最大的喜悦值是多少,并求出使夏川得到这个喜悦值,季堂的期 望购买次数。
输入
第一行,一个整数N,表示有N种礼物。
接下来N行,每行一个实数Pi和正整数Wi,表示第i种礼物被拿出来的概率和 可以获得喜悦值。
输出
第一行,一个整数表示可以获得的最大喜悦值。
第二行,一个实数表示获得这个喜悦值的期望购买次数,保留3位小数
样例输入
3
0.1 2
0.2 5
0.3 7
样例输出
14
12.167
提示
对于10%的数据,N = 1
对于30%的数据,N ≤ 5
对于100%的数据,N ≤ 20 ,0 < Wi ≤ 10^9 ,0 < Pi ≤ 1且∑Pi ≤ 1
考试心路历程
看到概率与期望一脸懵逼,完全把概率与期望那点知识给忘干净了。
尝试硬推式子,把12.167来回除以样例输入中的数字,啥规律也没找到。。。
只好尝试去骗10%,结果没保留三位导致w0。
题解
看到数据范围N<=20,状压dp的标志性数据范围。
正着枚举不好说,我们倒着考虑如何进行状态转移(我觉得主要是为了适应lowbit操作取出末位1)
所以我们的初始状态就是f[(1<<n)-1],答案为f[0]。
$f[i]=\Sigma{p[k]*f[j]}$(j为比i多买一件物品的状态,k就是多买的那件物品)$+(1-\Sigma{p[k]})$(买到已经买到的或者买到空自己转移回自己的概率)$*f[i]+1$
两边都出现了f[i],我们移项解决。
$f[i]=(\Sigma{p[k]*f[j]}+1)/(\Sigma{p[k]})$
然后转移就行了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include<cmath>
#define rint register int
using namespace std;
int n;
long long wi[],sum;
double qi[],dp[(<<)+];
inline long long lowbit(long long t){return t&(-t);}
int main()
{
scanf("%d",&n);
for(rint i=;i<=n;++i)
{
scanf("%lf %lld",&qi[i],&wi[i]);
sum+=wi[i];
}
for(rint i=(<<n)-;i>=;--i)
{
double sm=0.0;
for(rint j=;j<=n;++j)
{
if(!((<<(j-))&i))
{
dp[i]+=qi[j]*dp[i|(<<(j-))];
sm+=qi[j];
}
}
dp[i]=(dp[i]+)/sm;
}
printf("%lld\n%.3lf\n",sum,dp[]);
}