- bzoj4720: [Noip2016]换教室
- HDU 3853 LOOPS
- hdu 4035 Maze
- HDU 4336Card Collector
- zoj3640Help Me Escape
- zoj3380 Patchouli’s Spell Cards
- Poj3071 Football
- sgu495 Kids and Prizes
- POJ 2151Check the difficulty of problems
- HDU 4089 Activation
- HDU 4405 Aeroplane chess
- ZOJ 3329 One Person Game
- POJ 2096 Collecting Bugs
- cf148D Bag of mice
bzoj4720: [Noip2016]换教室
//https://www.luogu.org/blog/user22136/solution-p1850
#include<bits/stdc++.h>
using namespace std;
double w1,w2,w3,w4,dis[302][302],f[2002][2],c[2002],z,ans;
int n,m,v,e,i,j,k,a[2002],b[2002],x,y;
int main(){
scanf("%d%d%d%d",&n,&m,&v,&e);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=n;i++) scanf("%d",&b[i]);
for (i=1;i<=n;i++) scanf("%lf",&c[i]);
for (i=1;i<=v;i++)
for (j=1;j<i;j++) dis[i][j]=dis[j][i]=1e9;
for (i=1;i<=e;i++) scanf("%d%d%lf",&x,&y,&z),dis[x][y]=dis[y][x]=min(dis[x][y],z);
for (k=1;k<=v;k++)
for (i=1;i<=v;i++)
for (j=1;j<i;j++) dis[i][j]=dis[j][i]=min(dis[i][j],dis[i][k]+dis[k][j]);
for (i=0;i<=m;i++) f[i][0]=f[i][1]=1e9;
f[0][0]=f[1][1]=0;
for (i=2;i<=n;i++){
w1=dis[a[i-1]][a[i]];
w2=dis[b[i-1]][a[i]]*c[i-1]+dis[a[i-1]][a[i]]*(1-c[i-1]);
w3=dis[a[i-1]][b[i]]*c[i]+dis[a[i-1]][a[i]]*(1-c[i]);
w4=dis[b[i-1]][b[i]]*c[i-1]*c[i]+dis[b[i-1]][a[i]]*c[i-1]*(1-c[i])+
dis[a[i-1]][a[i]]*(1-c[i-1])*(1-c[i])+dis[a[i-1]][b[i]]*(1-c[i-1])*c[i];
for (j=min(i,m);j>=0;j--){
f[j][0]=min(f[j][0]+w1,f[j][1]+w2);
if (j) f[j][1]=min(f[j-1][0]+w3,f[j-1][1]+w4);
}
}
ans=1e9;
for (i=0;i<=m;i++) ans=min(ans,min(f[i][0],f[i][1]));
printf("%.2lf",ans);
}HDU 3853 LOOPS
/*https://www.cnblogs.com/kuangbin/archive/2012/10/03/2711140.html dp[i][j]表示(i,j)到(R,C)需要消耗的能量 则：dp[i][j]=p1[i][j]*dp[i][j]+p2[i][j]*dp[i][j+1]+p3[i][j]*dp[i+1][j]+2; 化简得到： dp[i][j]=p2[i][j]*dp[i][j+1]/(1-p1[i][j])+p3[i][j]*dp[i+1][j]/(1-p1[i][j])+2/(1-p1[i][j]); 注意一种情况就是p1[i][j]==1的情况。 题目只是保证答案小于1000000.但是有的点可能永远都不可能到达的。 所以这样的点出现p1[i][j]是允许的。 否则就会WA了。*/
#include<bits/stdc++.h>
using namespace std;
const int N=1003;
int r,c,i,j;
double p1[N][N],p2[N][N],p3[N][N],f[N][N];
int main(){
while (~scanf("%d%d",&r,&c)){
for (i=1;i<=r;i++)
for (j=1;j<=c;j++) scanf("%lf%lf%lf",&p1[i][j],&p2[i][j],&p3[i][j]);
memset(f,0,sizeof(f));
for (i=r;i;i--)
for (j=c;j;j--)
if ((i!=r || j!=c) && 1-p1[i][j]>1e-6)
f[i][j]=(f[i][j+1]*p2[i][j]+f[i+1][j]*p3[i][j]+2)/(1-p1[i][j]);
printf("%.3lf\n",f[1][1]);
}
}hdu 4035 Maze
/*https://www.cnblogs.com/kuangbin/archive/2012/10/03/2711108.html dp求期望的题。 题意： 有n个房间，由n-1条隧道连通起来，实际上就形成了一棵树， 从结点1出发，开始走，在每个结点i都有3种可能： 1.被杀死，回到结点1处（概率为ki） 2.找到出口，走出迷宫 （概率为ei） 3.和该点相连有m条边，随机走一条 求：走出迷宫所要走的边数的期望值。 设 E[i]表示在结点i处，要走出迷宫所要走的边数的期望。E[1]即为所求。 叶子结点： E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1); = ki*E[1] + (1-ki-ei)*E[father[i]] + (1-ki-ei); 非叶子结点：（m为与结点相连的边数） E[i] = ki*E[1] + ei*0 + (1-ki-ei)/m*( E[father[i]]+1 + ∑( E[child[i]]+1 ) ); = ki*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei)/m*∑(E[child[i]]) + (1-ki-ei); 设对每个结点：E[i] = Ai*E[1] + Bi*E[father[i]] + Ci; 对于非叶子结点i，设j为i的孩子结点，则 ∑(E[child[i]]) = ∑E[j] = ∑(Aj*E[1] + Bj*E[father[j]] + Cj) = ∑(Aj*E[1] + Bj*E[i] + Cj) 带入上面的式子得 (1 - (1-ki-ei)/m*∑Bj)*E[i] = (ki+(1-ki-ei)/m*∑Aj)*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei) + (1-ki-ei)/m*∑Cj; 由此可得 Ai = (ki+(1-ki-ei)/m*∑Aj) / (1 - (1-ki-ei)/m*∑Bj); Bi = (1-ki-ei)/m / (1 - (1-ki-ei)/m*∑Bj); Ci = ( (1-ki-ei)+(1-ki-ei)/m*∑Cj ) / (1 - (1-ki-ei)/m*∑Bj); 对于叶子结点 Ai = ki; Bi = 1 - ki - ei; Ci = 1 - ki - ei; 从叶子结点开始，直到算出 A1,B1,C1; E[1] = A1*E[1] + B1*0 + C1; 所以E[1] = C1 / (1 - A1); 若 A1趋近于1则无解... */
#include<bits/stdc++.h>
using namespace std;
const int N=10003;
const double eps=1e-9;
struct node{
int to,ne;
}E[N<<1];
int T,i,x,y,h[N],tot,n,Case;
double A[N],B[N],C[N],k[N],e[N];
void add(int x,int y){
E[++tot]=(node){y,h[x]};
h[x]=tot;
}
bool dfs(int u,int pre){
int m=0;
double ta=0,tb=0,tc=0,t=1-k[u]-e[u];
for (int i=h[u],v;i;i=E[i].ne,m++)
if ((v=E[i].to)!=pre){
if (!dfs(v,u)) return 0;
ta+=A[v];tb+=B[v];tc+=C[v];
}
ta*=t/m;tb*=t/m;tc*=t/m;
A[u]=k[u]+ta;
B[u]=t/m;
C[u]=t+tc;
if (fabs(1-tb)<eps) return 0;
A[u]/=1-tb;
B[u]/=1-tb;
C[u]/=1-tb;
return 1;
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);
tot=0;
memset(h,0,(n+1)<<2);
for (i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
for (i=1;i<=n;i++) scanf("%lf%lf",&k[i],&e[i]),k[i]/=100,e[i]/=100;;
printf("Case %d: ",++Case);
if (dfs(1,0) && fabs(1-A[1])>eps) printf("%.6lf\n",C[1]/(1-A[1]));
else printf("impossible\n");
}
}HDU 4336Card Collector
/*https://www.cnblogs.com/kuangbin/archive/2012/10/06/2713089.html*/
#include<bits/stdc++.h>
using namespace std;
int n,i,j;
double p[20],f[1<<20],sum,s;
int main(){
while (~scanf("%d",&n)){
for (i=0;i<n;i++) scanf("%lf",&p[i]);
f[(1<<n)-1]=0;
for (i=(1<<n)-2;i>=0;i--){
s=0;sum=1;
for (j=0;j<n;j++)
if (!(i&(1<<j))) sum+=p[j]*f[i|(1<<j)],s+=p[j];
f[i]=sum/s;
}
printf("%.5lf\n",f[0]);
}
}zoj3640Help Me Escape
//https://blog.csdn.net/sprithy_dream/article/details/8044200
#include<bits/stdc++.h>
using namespace std;
double dp[200003];
int c[103],t[103],n,f,i;
double dfs(int x){
if (dp[x]>0) return dp[x];
for (int i=0;i<n;i++){
if (x>c[i]) dp[x]+=t[i];
else dp[x]+=1+dfs(x+c[i]);
}
return dp[x]/=n;
}
int main(){
while (~scanf("%d%d",&n,&f)){
for (i=0;i<n;i++) scanf("%d",&c[i]),t[i]=(1+sqrt(5))/2*c[i]*c[i];
memset(dp,0,sizeof(dp));
printf("%.3lf\n",dfs(f));
}
}zoj3380 Patchouli’s Spell Cards
# https://blog.csdn.net/s_h_r/article/details/49025111
import sys
C = [([0] * 110) for i in range(110)]
for i in range(101):
C[i][0] = C[i][i] = 1
for j in range(1, i):
C[i][j] = C[i-1][j] + C[i-1][j-1]
def GCD(a, b):
return a if not b else GCD(b, a % b)
while True:
try:
m, n, l = map(int, sys.stdin.readline().split())
if(l > m):
print('mukyu~')
continue
dp = [([0] * 110) for i in range(110)]
dp[0][0] = 1
for i in range(1, n+1):
for j in range(1, m+1):
for k in range(0, min(j+1, l)):
dp[i][j] += dp[i-1][j-k] * C[m-(j-k)][k]
Sum = pow(n, m)
ans = 0
for i in range(1, n+1):
ans += dp[i][m]
ans = Sum - ans;
gcd = GCD(ans, Sum)
print str(ans / gcd) + '/' + str(Sum / gcd)
except:
breakPoj3071 Football
/*https://blog.csdn.net/xuechelingxiao/article/details/38520105 dp[i][j]表示第 i 轮的时候，第 j 支队伍赢的概率 dp[i][j] = ∑(dp[i-1][j]*dp[i-1][k]*p[j][k]); 对于其中位运算，可以用一个二叉树来更直观的理解 (j>>(i-1))^1) 跟 (k>>(i-1)分别表示一个父节点的两个子节点， 当(j>>(i-1))^1) == (k>>(i-1)时，表明两个子节点是竞争关系，胜利者将更新到父节点。 */
#include<cstdio>
#include<cstring>
using namespace std;
int n,i,j,k;
double f[8][1<<7],p[1<<7][1<<7];
int main(){
while (~scanf("%d",&n)){
if (n==-1) break;
for (i=0;i<1<<n;i++)
for (j=0;j<1<<n;j++) scanf("%lf",&p[i][j]);
memset(f,0,sizeof(f));
for (i=0;i<1<<n;i++) f[0][i]=1;
for (i=1;i<=n;i++)
for (j=0;j<1<<n;j++)
for (k=0;k<1<<n;k++)
if (((j>>(i-1))^(k>>(i-1)))==1) f[i][j]+=f[i-1][j]*f[i-1][k]*p[j][k];
k=0;
for (i=1;i<1<<n;i++)
if (f[n][i]>f[n][k]) k=i;
printf("%d\n",k+1);
}
}sgu495 Kids and Prizes
/*https://blog.csdn.net/L__emon/article/details/44655971 题意：有n个奖品，奖品各自放在盒子里，m个人轮流选取，若盒中有奖品则拿走，但不管怎样，盒子依然放回。问得到奖品数的期望。 思路：1）数学推理 每个奖品不被选中的概率为(1-1/n)^m，那么每个奖品被选中的概率为1-(1-1/n)^m； 所以总期望为n*(1-(1-1/n)^m); 2）概率dp dp[i]表示到第i个人得到奖品数的期望；所以dp[i]等于上一个人得到的奖品数加上这个人得到的奖品数； 若此人得到了奖品则概率为(n-dp[i-1])/n， 若没得到则概率为dp[i-1]/n； 所以dp[i] = dp[i-1]+1*(n-dp[i-1])/n+0*dp[i-1]/n； */
#include<bits/stdc++.h>
using namespace std;
int n,m,i;
double x,ans;
int main(){
scanf("%d%d",&n,&m);
x=1;
for (i=1;i<=m;i++){
ans+=x;
x=(n-ans)/n;
}
printf("%.10lf",ans);
}POJ 2151Check the difficulty of problems
/*https://blog.csdn.net/u013200703/article/details/47705129 dp[i][j][k] 表示第i个人前面j道题做对了k道的期望 dp[i][j][k] = dp[i][j-1][k]*(1-p[i][j]) + dp[i][j-1][k-1]*p[i][j] */
#include<cstdio>
#include<cstring>
using namespace std;
int k,i,j,n,m,t;
double ans,cnt,sub,dp[35][35],p[35];
int main(){
while (scanf("%d%d%d",&m,&t,&n)){
if (!m && !t && !n) break;
sub=ans=1;
for (i=1;i<=t;i++){
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for (j=1;j<=m;j++) scanf("%lf",&p[j]);
for (j=1;j<=m;j++)
for (k=0;k<=j;k++){
dp[j][k]+=dp[j-1][k]*(1-p[j]);
if (k>=1) dp[j][k]+=dp[j-1][k-1]*p[j];
}
ans*=(1-dp[m][0]);
cnt=0;
for (j=1;j<n;j++) cnt+=dp[m][j];
sub*=cnt;
}
printf("%.3f\n",ans-sub);//这里如果是%.3lf就错了，不知道为什么
}
}HDU 4089 Activation
/*https://www.cnblogs.com/kuangbin/archive/2012/10/03/2710987.html 题意：有n个人排队等着在官网上激活游戏。Tomato排在第m个。 对于队列中的第一个人。有一下情况： 1、激活失败，留在队列中等待下一次激活（概率为p1) 2、失去连接，出队列，然后排在队列的最后（概率为p2） 3、激活成功，离开队列（概率为p3） 4、服务器瘫痪，服务器停止激活，所有人都无法激活了。 求服务器瘫痪时Tomato在队列中的位置<=k的概率 解析： 概率DP； 设dp[i][j]表示i个人排队,Tomato排在第j个位置，达到目标状态的概率(j<=i) dp[n][m]就是所求 j==1: dp[i][1]=p1*dp[i][1]+p2*dp[i][i]+p4; 2<=j<=k: dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4; k<j<=i: dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]; 化简： j==1: dp[i][1]=p*dp[i][i]+p41; 2<=j<=k: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1]+p41; k<j<=i: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1]; 其中: p=p2/(1-p1); p31=p3/(1-p1) p41=p4/(1-p1) 可以循环i=1->n 递推求解dp[i].在求解dp[i]的时候dp[i-1]就相当于常数了。 在求解dp[i][1~i]时等到下列i个方程 j==1: dp[i][1]=p*dp[i][i]+c[1]; 2<=j<=k:dp[i][j]=p*dp[i][j-1]+c[j]; k<j=i: dp[i][j]=p*dp[i][j]+c[j]; 其中c[j]都是常数了。上述方程可以解出dp[i]了。 首先是迭代得到 dp[i][i].然后再代入就可以得到所有的dp[i]了。 注意特判一种情况。就是p4<eps时候，就不会崩溃了，应该直接输出0 应要用滚动数组优化，否则内存要炸 */
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
double dp[2][2003],p1,p2,p3,p4,p,p31,p41,c[2003],tmp,pp[2003];
int n,m,i,j,k,x,xx;
int main(){
while (~scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)){
if (p4<eps){
printf("0.00000\n");
continue;
}
p=p2/(1-p1);
p31=p3/(1-p1);
p41=p4/(1-p1);
pp[0]=1;
for (i=1;i<=n;i++) pp[i]=p*pp[i-1];
dp[1][1]=p41/(1-p);
c[1]=p41;
x=0;xx=1;
for (i=2;i<=n;i++,x^=1,xx^=1){
for (j=2;j<=k;j++) c[j]=dp[xx][j-1]*p31+p41;
for (j=k+1;j<=i;j++) c[j]=dp[xx][j-1]*p31;
tmp=0;
for (j=1;j<=i;j++) tmp+=c[j]*pp[i-j];
dp[x][i]=tmp/(1-pp[i]);
dp[x][1]=p*dp[x][i]+c[1];
for (j=2;j<i;j++) dp[x][j]=p*dp[x][j-1]+c[j];
}
printf("%.5lf\n",dp[xx][m]);
}
}HDU 4405 Aeroplane chess
#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,pos[100003],u,v;
double dis[100003];
int main(){
while (~scanf("%d%d",&n,&m)){
if (!n && !m) break;
for (i=0;i<=n;i++) pos[i]=0;
for (i=0;i<m;i++) scanf("%d%d",&u,&v),pos[u]=v;
for (i=n;i<=n+6;i++) dis[i]=0;
for (i=n-1;i>=0;i--)
if (!pos[i]){
dis[i]=1;
for (j=1;j<=6;j++) dis[i]+=dis[i+j]/6;
}else dis[i]=dis[pos[i]];
printf("%.4lf\n",dis[0]);
}
}ZOJ 3329 One Person Game
/*http://www.cnblogs.com/kuangbin/archive/2012/10/03/2710648.html 题意：有三个骰子，分别有k1,k2,k3个面。 每次掷骰子，如果三个面分别为a,b,c则分数置0，否则加上三个骰子的分数之和。 当分数大于n时结束。求游戏的期望步数。初始分数为0 设dp[i]表示达到i分时到达目标状态的期望，pk为投掷k分的概率，p0为回到0的概率 则dp[i]=∑(pk*dp[i+k])+dp[0]*p0+1; 都和dp[0]有关系，而且dp[0]就是我们所求，为常数 设dp[i]=A[i]*dp[0]+B[i]; 代入上述方程右边得到： dp[i]=∑(pk*A[i+k]*dp[0]+pk*B[i+k])+dp[0]*p0+1 =(∑(pk*A[i+k])+p0)dp[0]+∑(pk*B[i+k])+1; 明显A[i]=(∑(pk*A[i+k])+p0) B[i]=∑(pk*B[i+k])+1 先递推求得A[0]和B[0]. 那么 dp[0]=B[0]/(1-A[0]); */
#include<bits/stdc++.h>
using namespace std;
int T,n,k1,k2,k3,k,i,j,a,b,c;
double A[603],B[603],p[103],p0;
int main(){
scanf("%d",&T);
while (T--){
scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
p0=1.0/k1/k2/k3;
memset(p,0,sizeof(p));
for (i=1;i<=k1;i++)
for (j=1;j<=k2;j++)
for (k=1;k<=k3;k++)
if (i!=a || j!=b || k!=c) p[i+j+k]+=p0;
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
for (i=n;i>=0;i--){
A[i]=p0;B[i]=1;
for (j=1;j<=k1+k2+k3;j++) A[i]+=A[i+j]*p[j],B[i]+=B[i+j]*p[j];
}
printf("%.16lf\n",B[0]/(1-A[0]));
}
}POJ 2096 Collecting Bugs
/*https://blog.csdn.net/roney_win/article/details/9822753 题意：一个软件有s个子系统，会产生n种bug。 某人一天发现一个bug，这个bug属于某种bug，发生在某个子系统中。 求找到所有的n种bug，且每个子系统都找到bug，这样所要的天数的期望。 需要注意的是：bug的数量是无穷大的，所以发现一个bug，出现在某个子系统的概率是1/s， 属于某种类型的概率是1/n。 解法： dp[i][j]表示已经找到i种bug，并存在于j个子系统中，要达到目标状态的天数的期望。 显然，dp[n][s]=0，因为已经达到目标了。而dp[0][0]就是我们要求的答案。 dp[i][j]状态可以转化成以下四种： dp[i][j] 发现一个bug属于已经找到的i种bug和j个子系统中 dp[i+1][j] 发现一个bug属于新的一种bug，但属于已经找到的j种子系统 dp[i][j+1] 发现一个bug属于已经找到的i种bug，但属于新的子系统 dp[i+1][j+1]发现一个bug属于新的一种bug和新的一个子系统 以上四种的概率分别为： p1 = i*j / (n*s) p2 = (n-i)*j / (n*s) p3 = i*(s-j) / (n*s) p4 = (n-i)*(s-j) / (n*s) 又有：期望可以分解成多个子期望的加权和，权为子期望发生的概率，即 E(aA+bB+...) = aE(A) + bE(B) +... 所以： dp[i,j] = p1*dp[i,j] + p2*dp[i+1,j] + p3*dp[i,j+1] + p4*dp[i+1,j+1] + 1; 整理得： dp[i,j] = ( 1 + p2*dp[i+1,j] + p3*dp[i,j+1] + p4*dp[i+1,j+1] )/( 1-p1 ) = ( n*s + (n-i)*j*dp[i+1,j] + i*(s-j)*dp[i,j+1] + (n-i)*(s-j)*dp[i+1,j+1] )/( n*s - i*j ) */
#include<cstdio>
#include<cstring>
using namespace std;
int i,j;
double ns,f[1003][1003],n,s;
int main(){
scanf("%lf%lf",&n,&s);
ns=n*s;
for (i=n;i>=0;i--)
for (j=s;j>=0;j--)
if (i!=n || j!=s) f[i][j]=(f[i+1][j]*(n-i)*j+f[i][j+1]*i*(s-j)+f[i+1][j+1]*(n-i)*(s-j)+ns)/(ns-i*j);
printf("%.4f\n",f[0][0]);
}cf148D Bag of mice
/*http://www.cnblogs.com/kuangbin/archive/2012/10/04/2711184.html 题意： 原来袋子里有w只白鼠和b只黑鼠 龙和王妃轮流从袋子里抓老鼠。谁先抓到白色老师谁就赢。 王妃每次抓一只老鼠，龙每次抓完一只老鼠之后会有一只老鼠跑出来。 每次抓老鼠和跑出来的老鼠都是随机的。 如果两个人都没有抓到白色老鼠则龙赢。王妃先抓。 问王妃赢的概率。 解析： 设dp[i][j]表示现在轮到王妃抓时有i只白鼠，j只黑鼠，王妃赢的概率 明显 dp[0][j]=0,0<=j<=b;因为没有白色老鼠了 dp[i][0]=1,1<=i<=w;因为都是白色老鼠，抓一次肯定赢了。 dp[i][j]可以转化成下列四种状态： 1、王妃抓到一只白鼠，则王妃赢了，概率为i/(i+j); 2、王妃抓到一只黑鼠，龙抓到一只白鼠，则王妃输了，概率为j/(i+j)*i/(i+j-1). 3、王妃抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只黑鼠，则转移到dp[i][j-3]。 概率为j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2); 4、王妃抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只白鼠，则转移到dp[i-1][j-2]. 概率为j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2); 当然后面两种情况要保证合法，即第三种情况要至少3只黑鼠，第四种情况要至少2只白鼠 */
#include<bits/stdc++.h>
using namespace std;
int i,j,w,b;
double f[1003][1003];
int main(){
while (~scanf("%d%d",&w,&b)){
memset(f,0,sizeof(f));
for (i=1;i<=w;i++) f[i][0]=1;
for (i=1;i<=w;i++)
for (j=1;j<=b;j++){
f[i][j]=1.0*i/(i+j);
if (j>=3) f[i][j]+=1.0*j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*f[i][j-3];
if (j>=2) f[i][j]+=1.0*j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*f[i-1][j-2];
}
printf("%.10lf\n",f[w][b]);
}
}
京公网安备 11010502036488号