看心情填坑

http://poj.org/problem?id=3028

一眼迭代卡精度，然后发现牛仔是存在策略的_(:зゝ∠)_不能直接上。

n<=13，两眼状压DP，考虑dp[i][j][k]，i表示当前人的存活状况，j表示当前哪个人shoot，第k个人的存活期望概率。空间O(2^n*n*n)可以接受。初始化dp[1<<i][i][i]=1;dp[1<<i][i][j]=0;

然后我们发现这个dp是有环的不是很好搞_(:зゝ∠)_

定义几个东西：next(s,i)表示存活状况为s的时候在i之后下一个shoot的人,a[i]是第i个人的命中率

显然dp[i][j][k]只会由之后的状态转移过来，也就是说在处理dp[i][j][k]时它可以到达的所有状态都已经处理好了，那么显然我们对于一个状态i，可以预处理出每一个人射击的目标以及每一个next(i,k)。

考虑每一个dp[i][j][k]，会有pi=$\prod_{j\in i}a[j]$的概率转移到自己，那么假设一个状态对dp[i][j][k]有f的贡献，那么实际上它的贡献是f/(1-pi)。

对于dp[i][j][k],dp[i][next(i,j)][k],dp[i][next(i,next(i,j))][k]....，它们的转移情况其实是一个存在外向边的环（本人语文差，自己YY一下）。那么我们现在有两个状态dp[i][a][k],dp[i][b][k]，前一个状态假如射中了，也就是脱离了这个状态转移的环，假设这样k存活的概率是f，那么它对dp[i][b][k]的贡献为f*(b之后一直到a前一个人全部射空的概率)这样我们就可以做了。dp[i][j][k]可以由这个状态转移的环之中所有外向的边指向的状态转移过来啊好难讲(╯‵□′)╯︵┻━┻问题也就解决了。

还有就是要注意一下一个人有多个射击目标的情况，期望要求平均值

#include<cstdio>
#include<iostream>
using namespace std;
double a[13];
double dp[8192][13][13];
int kill[13][13];
double b[13];
int n,test;
int next(int s,int x){
	for(int i=x+1;i<n;i++)if(s&(1<<i))return i;
	for(int i=0;i<=x;i++)if(s&(1<<i))return i;
}
double abs(double k){return k>0?k:-k;}
void pre(int s){
	for(int x=0;x<n;x++)if((1<<x)&s){
		double max=0;
		for(int y=0;y<n;y++)if((x!=y)&&((1<<y)&s)){
			if(abs(dp[s^(1<<y)][next(s^(1<<y),x)][x]-max)<1e-12){
				kill[x][0]++;
				kill[x][kill[x][0]]=y;
			}
			if(dp[s^(1<<y)][next(s^(1<<y),x)][x]-max>1e-12){
				max=dp[s^(1<<y)][next(s^(1<<y),x)][x];
				kill[x][0]=1;
				kill[x][kill[x][0]]=y;
			}
		}
	}
}
int main(){
	scanf("%d",&test);
	while(test--){
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			scanf("%lf",&a[i]);
			a[i]/=100;
		}
		for(int i=0;i<(1<<n);i++)
			for(int j=0;j<n;j++)
				for(int k=0;k<n;k++)dp[i][j][k]=0;
		for(int i=1;i<(1<<n);i++){
			int j;
			double tot=1;
			for(j=0;j<n;j++){
				if((1<<j)==i){
					dp[i][j][j]=1;
					break;
				}
				if((1<<j)&i)tot*=1-a[j];
			}
			if((1<<j)==i)continue;
			for(j=0;j<n;j++)kill[j][0]=0;
			pre(i);
			tot=1-tot;
			for(int x=0;x<n;x++)if((1<<x)&(i)){
				for(int y=0;y<n;y++)if((1<<y)&(i)){
					double sum=0;
					for(int z=1;z<=kill[y][0];z++){
						int k=next(i^(1<<kill[y][z]),y);
					    sum+=dp[i^(1<<kill[y][z])][k][x]; 
					}
					sum/=kill[y][0];
					b[y]=sum*a[y];
				}
				for(int y=0;y<n;y++)if((1<<y)&(i)){
					double sum=0,times=1;
					for(int z=y;z<n;z++)if((1<<z)&(i)){
						sum+=b[z]*times;
              			times*=(1-a[z]);
              		}
					for(int z=0;z<y;z++)if((1<<z)&(i)){
						sum+=b[z]*times;
              			times*=(1-a[z]);
              		}
					dp[i][y][x]=sum/tot;
				}
			}
		}
		for(int i=0;i<n;i++)printf("%.2lf ",dp[(1<<n)-1][0][i]*100);
		puts("");
	}
}