 /**//*
题意:父亲有f元、母亲有m元,盒子里有nb个蓝球,nr个红球
每次取一个球,蓝球的话父亲赢母亲1元,红球的话。。。
球会放回,问游戏结束的期望
设E[i]表示父亲现在有i元离游戏结束还需要的次数的期望
有E[i] = pf*E[i+1]+pm*E[i-1]+1
E[f+m]=E[0]=0
E[i]与E[i-1],E[i+1]有关 我们求的是E[f]
可以知道有环。有环的话类似zoj3329 用E[f]去表示其他 最后再得到E[f] = F(E[f])
E[i] = x[i]E[f]+y[i] 但算不出
表示成e[i] = a[i]e[f]+b[i]e[i+1]+c[i] 最后再修改一下!!

高斯消元需要O(n3) n<=10000 TLE
*/
#include<cstdio>
#include<cstring>

const int MAXN = 20010;

double a[MAXN],b[MAXN],c[MAXN];

int main()
  {
int T;
for(scanf("%d",&T);T--;)
 {
int f,m,nb,nr,fm;
scanf("%d%d%d%d",&f,&m,&nb,&nr);
double pm = nr/(nb+nr+0.0),pf = 1 - pm;
fm = f+m;

//由于有环,尝试用e[f]去表示其他 e[i] = a`[i]e[f]++c`[i]
//如果直接这样表示还不能算出来
//再设e[i] = a[i]e[f]+b[i]e[i+1]+c[i]
//这样就比较容易算了 lyd Orz
//林宇东 20:47:26
//加b[i]是手段,只是在想怎么表示e[i+1],然后再把它去掉

a[f] = 1.0,b[f] = c[f] = 0.0;
a[0] = b[0] = c[0] = 0.0;
a[fm] = b[fm] = c[fm] = 0.0;

//e[i] = a[i]e[f]+b[i]e[i+1]+c[i]
for(int i=f+1;i<fm;i++)
 {
double tmp = 1-pm*b[i-1];
a[i] = a[i-1]*pm/tmp;
b[i] = pf/tmp;
c[i] = (1+pm*c[i-1])/tmp;
}
//e[i] = a`[i]e[f]+c[i]
for(int i = fm-1;i>f;i--)
 {
a[i]+=b[i]*a[i+1];
c[i]+=b[i]*c[i+1];
}
//e[i] = a[i]e[f]+b[i]e[i-1]+c[i]
for(int i=f-1;i;i--)
 {
double tmp = 1-pf*b[i+1];
a[i] = a[i+1]*pf/tmp;
b[i] = pm/tmp;
c[i] = (1+pf*c[i+1])/tmp;
}
//e[i] = a`[i]e[f]+c[i]
for(int i = 1;i<f;i++)
 {
a[i]+=b[i]*a[i-1];
c[i]+=b[i]*c[i-1];
}
printf("%.0f\n",(1+pm*c[f-1]+pf*c[f+1])/(1-pm*a[f-1]-pf*a[f+1]));
}
return 0;
}

 /**//*
网上还提供另外的做法
E[i] = pm*E[i-1]+pf*E[i+1]+1
整理,列出增广矩阵 发现每一行只有3个系数-pm , 1 , -pf , 1
所以先从上到下消去对角线下的,再从下到上消去对角线上的即可了O(n)

有通用的方法:追赶法
*/

#include<cstdio>

const int MAXN = 20010;

double a[MAXN],b[MAXN],c[MAXN],d[MAXN];

int main()
  {
int T;
for(scanf("%d",&T);T--;)
 {
int f,m,fm,nb,nr;
scanf("%d%d%d%d",&f,&m,&nb,&nr);
fm = f+m;
double pm = nr/(nr+nb+0.0) , pf = 1-pm;
b[0]=1.0,a[0]=c[0]=d[0]=0.0;
b[fm]=1.0,a[fm]=c[fm]=d[fm]=0.0;
for(int i=1;i<fm;i++)
 {
double k = -pm/b[i-1];
d[i]=1.0-d[i-1]*k;
b[i]=1.0-c[i-1]*k;
c[i]=-pf;
}
for(int i=fm-1;i>=f;i--)
 {
double k = c[i]/b[i+1];
d[i]-=d[i+1]*k;
}
printf("%.0f\n",d[f]/b[f]);
}
return 0;
}
列出方程后,高斯消元O(n^3)太慢了,而且精度损失也比较大 所以题目给出的应该不是用高斯消元吧~~~挖掘方程的特点 hit 2914 zoj3329 都是方程有环的,都将要求的变量看成未知量,然后去表示其他,E[i] = fx(i) 最后推到自己E[x] = fx(x)
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|