题目描述
n fish, numbered from 1 to n, live in a lake. Every day right one pair of fish meet, and the probability of each other pair meeting is the same. If two fish with indexes i and j meet, the first will eat up the second with the probability aij, and the second will eat up the first with the probability aji = 1 - aij. The described process goes on until there are at least two fish in the lake. For each fish find out the probability that it will survive to be the last in the lake.
价值
刷到了个好题哈哈哈哈，复习了状态压缩，复习了记忆化搜索，还练习了概率，思路已经给出
#include<bits/stdc++.h>
using namespace std;
/*
这是注意点
注意优先级（括号）if((pan&zt)==pan)
还有，确定一个状态后，这个状态由上一次转过来的可能性是所有活着的鱼遇见并吃掉这个鱼的概率和
还有记得记忆化搜索（TLE*3）
这是思路
最开始没有思路，后来发现读错题目了，每天只有一对鱼相遇，然后必死一个（不是每天少一半)
应该还是dp吧，表示第i条鱼在第j天存活的概率
然后某一天剩余鱼的数量也要考虑（概率会变化）
剩余数量显然是n-i+1
但是死了哪些鱼我也要确切记住，不然第二个概率难计算
那这样下来和暴力搜索没区别了。。。。。。
等等，鱼只有死亡和存活的区别
状态压缩！ 但不是旅行商问题（我只自学过旅行商问题怎么写，但应该差不多吧）
只会记忆化搜索
然后2的18次方不会超
死了为0,活着1
我只写过一次状态压缩dp，可以看看我的博客
https://www.cnblogs.com/linghusama/p/17403383.html
铃兰可爱内
*/
int n;
double dp[1<<20];//记忆化搜索
double w[25][25];
double findd(int zt,int las){
if(dp[zt]!=-1){
return dp[zt];
}
if((1<<(n+1))-2==zt){
return 1;//全部存活 (1111111111111111110)
}
double ret=0;
for(int i=1;i<=n;i++){
int pan=1<<i;
if((pan&zt)==pan){//zt一位上是1的话,说明这个本来活着的，不能再复活了
continue;
}
else{//这个鱼死了，上一次可能就是他被吃了，找他的概率
for(int k=1;k<=n;k++){//枚举这一次吃它的鱼
int m=1<<k;
if((m&zt)==m){
ret+=1.0*findd((zt|pan),las+1)*w[k][i]* 2/((las)*(las+1));//最后一步把这个鱼给吃了，注意我要枚举吃掉这个鱼的鱼是哪个
}
else{
continue;
}
}
}
}
dp[zt]=ret;
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
cout.precision(7);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin >> w[i][j];
}
}
for(int i=1;i<=1<<(n+1);i++){
dp[i]=-1;
}
for(int i=1;i<=n;i++){
cout<<findd(1<<i,1)<<" ";
}
}