/**//* 要从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
搜索
最新评论
|
|