礼物 【NOIP2016提高A组8.12】

题目

夏川的生日就要到了。作为夏川形式上的男朋友，季堂打算给夏川买一些生日礼物。 商店里一共有种礼物。夏川每得到一种礼物，就会获得相应喜悦值Wi（每种礼物的喜悦值不能重复获得）。 每次，店员会按照一定的概率Pi（或者不拿出礼物），将第i种礼物拿出来。季堂每次都会将店员拿出来的礼物买下来。 众所周知，白毛切开都是黑的。所以季堂希望最后夏川的喜悦值尽可能地高。 求夏川最后最大的喜悦值是多少，并求出使夏川得到这个喜悦值，季堂的期望购买次数

样例输入： 第一行，一个整数N，表示有N种礼物。 接下来N行，每行一个实数Pi和正整数Wi，表示第i种礼物被拿出来的概率和可以获得喜悦值。 3 0.1 2 0.2 5 0.3 7

样例输出： 第一行，一个整数表示可以获得的最大喜悦值。 第二行，一个实数表示获得这个喜悦值的期望购买次数，保留3位小数。 14 12.167

数据范围： 对于10%的数据，N = 1 对于30%的数据，N ≤ 5 对于100%的数据，N ≤ 20 ，0 < Wi ≤ 10^9 ，0 < Pi ≤ 1且∑Pi ≤ 1 注意：本题不设spj

---

剖解题目

题目讲的很清楚了- -|||。

---

思路

期望类型的题目我一直是一脸懵逼的，在比赛时连样例我也不会解释，所以也没什么思路，不过当时因为看到N比较小，对状压是有考虑，但是没有dp出来。

---

解法

10%：友情送分。 30%：状压DP，设 fS 表示从当前得到的礼物的情况到得到目标所需要的期望步数，S是一个二进制表示的状态。转移就是 fS=∑(fS′∗p[i])+(fS∗(1−∑p[i]))+1 ，用高斯消元。时间复杂度为 O(（2n）3) 。（然而我并不会打高斯，所以直接跳过此部分分） 100%：还是这个方程式，但是我们发现右边存在一个 fS 是与左边一样的，我们便可以移项，将 fS 部分移到左边，然后化简后将系数移回到右边除去。时间复杂度是 O(2n) 。

---

代码

#include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define ll long long using namespace std; const int maxn=21; double p[maxn],f[1<<maxn]; int n,w[maxn]; ll ans; int main() { scanf("%d",&n); p[n+1]=1; fo(i,1,n) { scanf("%lf%d",&p[i],&w[i]); ans+=(ll)w[i]; p[n+1]=p[n+1]-p[i]; } int N=1<<n; for(int x=N-2;x>=0;x--){ double up=1,down=1-p[n+1]; fo(j,1,n){ int k=x&(1<<(j-1)); if (k==0) up=up+p[j]*f[x|(1<<(j-1))]; else down=down-p[j]; } f[x]=up/down; } printf("%lld\n%.3lf",ans,f[0]); }