 /**//*
要从n<=13个人中通过黑白配多去少留(相等的话继续),如果只有两个人则剪刀石头布来选出一个苦力。
要求选出苦力所用时间的期望,还有哪些人最有可能成为苦力,及其成为苦力的概率。
给出每个人出黑、白、石头、剪刀、布的概率u,d,r,p,s
瞄到watashi博客上的枚举子集
我就尝试,dp[mask]表示当前这些人离目标的期望次数
然后转移就是枚举多少人出黑、白,如果两个人时就枚举石头、剪刀、布
dp[mask] = 1+∑up[sub]*down[other]*dp[bitcount[sub] < bitcount[other] ? sub : other] , other = mask ^ sub即other是sub关于mask的补集
不过这里有一些是bitcount[sub] = bitcount[other] 或者 bitcount[sub] = 0,bitcount[other] = 0的情况,此时转移到mask
将这些项移到左边去即可,我看watashi是不转移两种情况
而每个人成为苦力的概率时,是指"从初始状态到只剩一个人时(或者Infinity)的这个事件发生的概率"
就可以通过从最初dp[(1<<n)-1]不断乘以一些决策的概率转移到下一种事件
因为有可能一次决策后还是没有人去掉,这样mask还是变回到了mask
这里,我看watashi算概率时,只算那些有转移的事件。
比如状态1->1概率为p1,1->2为p2,1->3为p3 ,则认为从p1转移到p2的概率为 p2/(p2+p3),即分母是可以转移的状态的概率之和
我的理解是,即使转移到1,到最后结束时,肯定是转移到2或3!!!!
这样1转移到2的概率就为: p2+p1*p2+p1*p1*p2+ = p2*(1+p1+p1^2 ) = p2*(1-p1^n)/(1-p1) = p2/(1-p1)
其实也就是转移到1的概率最后还是会按比例分配到2,3,所以不用考虑转移到自身的
原来这个就是“归一化”

我之前以为每个人lose的概率是指这些人lose的ratio,这样他们之和就为1了
watashi:"不是的,你看样例就有一个是0.0% + 0.0% < 1的。加上死循环的概率之和才是1"

复杂度就是枚举子集再枚举子集,2^k*C(n,k) = (2+1)^n = 3^n
这题要先预处理一些东西,转移时直接用,不然会超时吧
可能看到n=13,n=12时就应该要猜到是O(3^n)的做法了,2010福州warm up D题就是O(3^12)

好了,到这里怎么算是比较明确的
但这题比较多的细节,比如inf,nan(not a number),要避免算出nan
如果说为了避免除0,当遇到分母时就赋值为自定义的INF时,注意这个INF继续参与运算后,结果不一定变为INF了
如(0.1*1e30+0.9*1)+1 << 1e30 !!!!!
所以即使除0,没事的,直接除,系统会给予以个inf的值

而inf的值参与运算时几个注意的地方:
inf*1e-300 还是inf
+inf + +inf = +inf 但+inf + -inf = nan
inf*0 = nan
0/0 = nan
inf/inf = nan
inf*inf = inf 符号跟平常乘法的一样
感觉跟数学的无穷大、无穷小的运算类似,0/0 , +∞ - +∞, ∞/∞ 等是未定义

g++的math.h就有isinf(),isfinite(),isnan()函数用了
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<ctime>
#include<bitset>

using namespace std;

const double EPS = 1e-8;

double dp[1<<13], u[13], d[13], r[13], p[13], s[13];
double up[1<<13], down[1<<13];
double lose[13][13];
int bitcount[1<<13];
string name[13];

int main()
  {
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
#endif
 for (int mask = 0; mask < (1<<13); mask ++) {
bitcount[mask] = bitcount[mask>>1] + (mask&1);
}
int T,n;
 for (scanf("%d", &T); T--; ) {
scanf("%d", &n);
 for (int i = 0; i < n; i ++) {
cin>>name[i];

cin>>u[i]>>d[i];
double sum = u[i] + d[i];
u[i] /= sum;
d[i] /= sum;

cin>>r[i]>>p[i]>>s[i];
sum = r[i]+p[i]+s[i];
r[i] /= sum;
p[i] /= sum;
s[i] /= sum;
}
up[0] = down[0] = 1.0;
 for(int mask = 1; mask < (1<<n); mask ++) {
int x;
 for(int i = 0; i < n ; i ++) {
 if(mask & (1<<i)) {
x = i;
break;
}
}
up[mask] = up[mask^(1<<x)]*u[x];
down[mask] = down[mask^(1<<x)]*d[x];
}
//x lose to y
 for(int x = 0; x < n; x++) {
 for(int y = 0; y < n ; y++) {
lose[x][y] = r[x]*p[y] + p[x]*s[y] + s[x]*r[y];
}
}

 for ( int mask = 1; mask < (1<<n) ; mask ++) {
 if(bitcount[mask] == 1) {
dp[mask] = 0.0;
 }else if(bitcount[mask] == 2) {
int x = -1, y;
 for(int i = 0; i < n ; i ++) {
 if(mask & (1<<i)) {
x == -1 ? x = i : y = i;
}
}
dp[mask] = 1.0 / (lose[x][y]+lose[y][x]);
 }else {
double div = 0, mul = 1.0;
 for(int sub = mask & (mask - 1) ; sub > 0 ; sub = mask & (sub - 1)) {
int other = mask ^ sub;
 if(bitcount[sub] != bitcount[other] && up[sub] > 0 && down[other] > 0) {//要判断>0,否则为0时跟下面的dp[<?sub:other]相乘就会为NaN!!!
div += up[sub]*down[other];
mul += up[sub]*down[other]*dp[bitcount[sub] < bitcount[other] ? sub : other];
}
}
dp[mask] = mul / div;
}
}
 if(dp[(1<<n) - 1] > 1e30) {
printf("Infinity ");
 }else {
printf("%.3f ", dp[(1<<n) - 1] );
}

double ans = 0;
fill(dp, dp+(1<<n), 0);
dp[(1<<n) -1] = 1.0;
 for (int mask = (1<<n) - 1; mask > 0 ; mask -- ) {
 if(dp[mask] == 0) {
continue;
}
 if(bitcount[mask] == 1) {
ans = max(ans, dp[mask]);
 }else if(bitcount[mask] == 2) {
int x = -1, y;
 for(int i = 0; i < n ; i ++) {
 if(mask & (1<<i)) {
x == -1 ? x = i : y = i;
}
}
 if(lose[x][y] + lose[y][x] > 0) {//0/0会算出NaN,而为0时,答案也就为0,不用算
dp[1<<x] += lose[x][y] / (lose[x][y] + lose[y][x]) * dp[mask];
dp[1<<y] += lose[y][x] / (lose[x][y] + lose[y][x]) * dp[mask];
}
 }else {
double div = 0;
 for(int sub = mask & (mask - 1) ; sub > 0 ; sub = mask & (sub - 1) ) {
int other = mask ^ sub;
 if(bitcount[sub] != bitcount[other] && up[sub] > 0 && down[other] > 0) {
div += up[sub]*down[other];
}
}
 if(div == 0) {
continue;
}
 for(int sub = mask & (mask - 1) ; sub > 0 ; sub = mask & (sub - 1) ) {
int other = mask ^ sub;
 if(bitcount[sub] != bitcount[other] && up[sub] > 0 && down[other] > 0) {
dp[bitcount[sub] < bitcount[other] ? sub : other] += up[sub]*down[other]/div*dp[mask];
}
}
}
}

vector<string> vt;
 for(int i = 0 ; i < n ; i ++ ) {
 if(fabs(dp[1<<i] - ans ) < EPS) {
vt.push_back(name[i]);
}
}
sort(vt.begin(), vt.end());
printf("%.3f%%\n", ans*100);
 for(vector<string>::iterator it = vt.begin() ; it != vt.end() ; it++) {
 if(it != vt.begin()) {
putchar(' ');
}
cout<<*it;
}
cout<<endl;
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|