http://acm.hdu.edu.cn/showproblem.php?pid=5985
作为队里负责动态规划的同学，做不出来好无奈啊。思考了一个下午，最好还是参考了别人的思想才写出来，数学啊！！！
这题随着K的增长，贡献的数值越来越少，所以只要K足够大（100左右就够了，一开始写30WA了），之后的就可以不考虑了。
那么对于每个K，我们又可以枚举每种硬币是最后留下来的那种，那么其他硬币必须是被耗尽的。但是还有一个隐藏要求，就是在第K次之前的一次时，其他硬币不能全部耗尽，不然就不存在第K次了！
这里千万不要用P(其余硬币在K-1次没有耗尽)*P(其余硬币在K次耗尽了)，这两个并不是独立事件！
因为K=1是不存在违反隐藏要求的情况的，之前必然有硬币。而K>=2时如果直接用P(i类硬币未用尽)*P(其余硬币用尽)则会包含之前就已经剩最后一种，然后再删掉一部分得到第K次依旧剩最后一种的情况。
所以在计算的时候，把之后还有硬币被消除的那一部分概率给删去，剩下的就能保证当前是最后一次了。（此部分存疑，个人认为即时这样做了，还是不对的，奈何这样写就AC，我改了就WA）
#include<iostream> #include <cstring> #include <string> #include <cstdio> #define LL long long using namespace std; const LL K=99; double dp[12][K][2];//0: at least 1:dead all int s[12]; double p[12]; double fastMi(double a,int b) { double mut=1; while(b) { if(b%2!=0) mut*=a; a*=a; b/=2; } return mut; } int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i=0; i<n; i++) scanf("%d %lf",&s[i],&p[i]); for(int i=0; i<n; i++) { for(int k=0; k<K; k++) { dp[i][k][1]=fastMi(1-fastMi(p[i],k),s[i]); dp[i][k][0]=1-dp[i][k][1]; } } if(n==1) { puts("1.000000"); continue; } for(int i=0; i<n; i++) { double ans=0.0; for(int k=1; k<K-1; k++) { double px=dp[i][k][0]-dp[i][k+1][0]; for(int j=0; j<n; j++) { if(j==i)continue; px*=dp[j][k][1]; } ans+=px; } if(i==n-1) printf("%.6f ",ans); else printf("%.6f ",ans); } } return 0; }