概率题。
本蒟蒻不会概率dp,于是手搓枚举。 反正爆枚够用
后记:SadBee的想法
考虑维护每队对上上一队/下一队的胜率。
只有两队最简单,用1乘即可
那多队呢?不如看成两队。
见:
P(1 胜) | = P(1 战胜 2)P(3 战胜 4)P(1 战胜 3) + P(1 战胜 2)P(4 战胜 3)P(1 战胜 4) |
P(2 胜) | = P(2 战胜 1)P(3 战胜 4)P(2 战胜 3) + P(2 战胜 1)P(4 战胜 3)P(2 战胜 4) |
P(3 胜) | = P(1 战胜 2)P(3 战胜 4)P(3 战胜 1) + P(2 战胜 1)P(3 战胜 4)P(3 战胜 2) |
P(4 胜) | = P(2 战胜 1)P(4 战胜 3)P(4 战胜 2) + P(1 战胜 2)P(4 战胜 3)P(4 战胜 1) |
中道崩殂的代码: |
#include<iostream>
#include<string.h>
using namespace std;
double p[130][130][8],dp[130];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n;
m=1<<n;
for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)cin>>p[i][j][0];
memset(dp,1.0,sizeof(dp));
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dp[2*j-1]*=p[2*j-1][j][i-1],
}
标签:int,3071,130,POJ,战胜,tie,dp
From: https://www.cnblogs.com/zan-mei-tai-yang/p/18393312