每次考dp我都会挂。
咳，我dp掌握真是差劲
每次期望dp都会挂掉。
首先见到期望一定要想dp，看到n的范围无脑想状压，
然后我就只想到这了。
dp方程式还是比较好想的，但是我依然想不出来
略经思考 颓题解
依然不会,随便写了个式子
i状态中不含j
$f[i]=\sum_\limits{j=1}^{j<=n} {f[j]\times p[j] }(买到之前没有的) $$+(1-p[i])\times {f[i]}(由自己转移过来(买到已经买过的)) $
$+1(什么也不买)$
显然不是i吖
然后
$f[i]=\sum_\limits{j=1}^{j<=n} {f[j]\times p[j] }(买到之前没有的) $ $+$ $(1-$$\sum_\limits{j=1}^{j<=n}p[j] )$ $\times f[i]+1(店员什么也没拿)$
观察，等式右面也有fi，如果我们楞做就是高斯消元了
那么移项得
$f[i]=$ $\frac{\sum_\limits{j=1}^{j<=n}f[j]\times p[j]+1} {\sum_\limits{j=1}^{j<=n} p[j]}$
转移就完了
#include<bits/stdc++.h> #define ll long long #define A 1<<24 double f[A],p[A]; ll n,m,sum=0,Smily; void turn(ll x,ll n) { ll t=x,num=0,xx[100]; while(x) xx[num++]=x%2,x/=2; for(ll i=num;i<n;i++)printf("0"); for(ll i=num-1;i>=0;i--)printf("%lld",xx[i]); puts(""); } using namespace std; int main() { scanf("%lld",&n); for(ll i=1;i<=n;i++){ scanf("%lf%lld",&p[i],&Smily); sum+=Smily; } printf("%lld\n",sum); for(ll i=(1<<n)-2;i>=0;i--){ double now=0; for(ll j=1;j<=n;j++){ if(!((1<<(j-1))&i)) f[i]+=f[i|(1<<(j-1))]*p[j],now+=p[j]; } // printf("f=%lf now=%lf\n",f[i],now); f[i]++; f[i]/=now; } // for(ll i=1;i<=(1<<n)-1;i++) // { // printf("%lf\n",f[i]); // } printf("%.3lf\n",f[0]); } View Code
转载于:https://www.cnblogs.com/znsbc-13/p/11196790.html
相关资源：Android直播礼物选择，送礼物，左右滑动，小圆点