概率dp专场

时间:2023-03-09 19:04:50
概率dp专场

概率dp专场

专题链接

第一题--poj3744 Scout YYF I  链接 (简单题)

算是递推题 如果直接推的话 会TLE 会发现 在两个长距离陷阱中间 很长一部分都是重复的 我用 a表示到达i-2步的概率 b表示到达i-1步的概率 c表示到达i步的概率

如果数很大的话 中间肯定会有重复的a,b,c 直接将i挪到最近的陷阱前一位 i = a[o]-1,大大节省时间。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
int x[];
int main()
{
int i,n,j;
double p;
while(cin>>n)
{
cin>>p;
for(i = ;i < n ;i++)
{
cin>>x[i];
}
sort(x,x+n);
double a = 1.0,b=0.0,c;
double ta = ,tb = ;
int o = ;
if(x[]==)
a = ;
else a = ;
for(i = ; i <= x[n-]+ ; i++)
{
if(i==x[o])
{
o++;
while(x[o]==x[o-])
o++;
c = ;
}
else
c = a*p+b*(1.0-p);
b = a;
a = c;
if(o<n&&fabs(ta-a)<eps&&fabs(tb-b)<eps)
i = x[o]-;
ta = a;
tb = b;
}
printf("%.7f\n",c);
}
return ;
}

第二题--poj3071Football(简单题)

dp[i][j] 表示第i场j赢的概率 那么可以写出方程dp[i][j] += dp[i-1][g]*p[j][g].

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 100000
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
double p[][];
double dp[][];
int pp[];
int main()
{
int i,j,n,g;
pp[] = ;
for(i = ;i <= ;i++)
pp[i] = pp[i-]*;
while(cin>>n)
{
if(n==-) break;
memset(dp,0.0,sizeof(dp));
int k = n;
n = pp[n];
for(i = ; i <=n ; i++)
for(j = ;j <= n; j++)
cin>>p[i][j];
for(i = ; i <=n ;i++)
{
if(i%)
dp[][i] = p[i][i+];
else
dp[][i] = p[i][i-];
}
for(i = ;i <= k ;i++)
{
for(j = ;j <= n ;j+=pp[i])
{
for(g = j; g < j+pp[i-] ; g++)
{
for(int e = j+pp[i-] ; e < j+pp[i] ; e++)
{
dp[i][g]+=dp[i-][g]*dp[i-][e]*p[g][e];
dp[i][e]+=dp[i-][e]*dp[i-][g]*p[e][g];
}
}
}
}
double maxz = ;
int ans;
for(i = ; i <= n ;i++)
{
if(maxz<dp[k][i])
{
maxz = dp[k][i];
ans = i;
}
//printf("%.5lf %d\n",dp[k][i],i);
}
cout<<ans<<endl;
}
return ;
}

第三题--CodeForces 148D(简单题)

刚开始看错了题意,以为一次跳出一个老鼠,按概率直接算,WA后发现dragon画的时候会另有一只跳出来,这样就根据跳出来的是黑还是白分两种情况计算。

如果当前是dragon轮 也就是(总数-剩余数)%3!=0 时  dp[i][j] = j/(i+j)*((j-1)/(i+j-1)*dp[i][j-2]+i/(i+j-1)*dp[i-1][j-1])

dp[i][j] 表示还有i只白老鼠及j只黑老鼠时princess赢的概率。 princess轮计算方式类似。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 1010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
double dp[N][N];
int main()
{
int i,a,b,j;
while(cin>>a>>b)
{
memset(dp,,sizeof(dp));
for(i = ;i <= a ; i++)
{
if((a+b-i)%==)
dp[i][] = ;
}
for(i = ; i <= a ;i++)
for(j = ;j <= b ;j++)
{
if((a+b-(i+j))%)
{
if(j>=)
dp[i][j] = j*1.0/(i+j)*((j-)*1.0/(i+j-)*dp[i][j-]+(i*1.0)/(i+j-)*dp[i-][j-]);
else
dp[i][j] = j*1.0/(i+j)*dp[i-][j-];
}
else
{
dp[i][j] = i*1.0/(i+j)+j*1.0/(i+j)*dp[i][j-];
}
//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
}
printf("%.9lf\n",dp[a][b]);
}
return ;
}

第四题--POJ 2151 Check the difficulty of problems

这个题正推不好推,可以求逆,dp[i][j][g]表示第i个队在前g个题里解决了j道题的概率 再令开一dd[i][j]累加和保存第i队最多解决了j道题的概率

这样依次求出每队解决大于1道题的概率减掉每队解决少于n道的概率 即为每队至少解决一道并且冠军队解决至少n道的概率

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 1010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
double dp[N][][],dd[N][];
double p[N][];
int main()
{
int i,j,n,m,t,g,e;
while(cin>>m>>t>>n)
{
if(!n||!m||!t) break;
memset(dp,0.0,sizeof(dp));
memset(dd,0.0,sizeof(dd));
for(i = ; i <= t ; i++)
{
dp[i][][] = 1.0;
for(j = ; j <= m ;j++)
{
cin>>p[i][j];
dp[i][][j] = (1.0-p[i][j])*dp[i][][j-];
}
dd[i][] = dp[i][j][m];
}
for(i = ;i <= t ;i++)
for(j = ;j <= m ;j++)
{
e = ;
for(g = j ;g <= m ; g++)
{
dp[i][j][g] = dp[i][j-][g-]*p[i][g]+dp[i][j][g-]*(-p[i][g]);
}
dd[i][j] = dd[i][j-]+dp[i][j][m];
}
double ans = 1.0,ss=1.0;
for(i = ; i <= t; i++)
{
ans*=dd[i][m]-dd[i][];
ss*=dd[i][n-]-dd[i][];
}
printf("%.3f\n",ans-ss);
}
return ;
}

第五题--POJ 2096 Collecting Bugs (简单期望题)

学习完这题可以了解到这一类期望题的解法,确定好一个边界状态,可能是初态也可能是终态,然后向后或向前推。

这题可以确定的为终态,dp[n][s] = 0. 然后倒推就可以了 dp[i][j] = dp[i][j+1]*(s-j)*1.0/s*i/n+dp[i+1][j]*(n-i)/n*j/s+dp[i+1][j+1]*(n-i)/n*(s-j)/s+1+i*j*1.0/n/s;

一个方程一个未知数,dp[0][0]即为答案。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 1010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
double dp[N][N];
int main()
{
int n,s,i,j;
while(cin>>n>>s)
{
memset(dp,0.0,sizeof(dp));
for(i = n ; i >= ;i--)
for(j = s ; j >= ;j--)
{
if(i==n&&j==s) continue;
dp[i][j] = dp[i][j+]*(s-j)*1.0/s*i/n+dp[i+][j]*(n-i)/n*j/s+
dp[i+][j+]*(n-i)/n*(s-j)/s+;
dp[i][j] = dp[i][j]/(-(i*j*1.0/n/s)); }
printf("%.4f\n",dp[][]);
}
return ;
}

第六题--HDU 3853 LOOPS(简单期望题)

与上一题类似,可以确定终态 dp[r][c] = 0.然后根据可走的概率进行倒推,注意可能会有无解的情况,p[i][j][0]=1就会进入死循环。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 1010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
double dp[N][N];
double p[N][N][];
int main()
{ int i,j,r,c;
while(cin>>r>>c)
{
memset(dp,0.0,sizeof(dp));
for(i = ; i <= r ; i++)
{
for(j = ; j <= c; j++)
{
for(int g = ; g < ; g++)
scanf("%lf",&p[i][j][g]);
}
}
for(i = r ; i >= ; i--)
{
for(j = c ; j >= ; j--)
{
if(i==r&&j==c) continue;
dp[i][j] = dp[i+][j]*p[i][j][]+dp[i][j+]*p[i][j][]+;
if(fabs(-p[i][j][])<eps) continue;
dp[i][j] = dp[i][j]/(-p[i][j][]);
}
}
printf("%.3lf\n",dp[][]);
}
return ;
}

第七题--HDU 4405 Aeroplane chess (简单期望题)

投掷骰子的问题,也是一样的问题,确定终态求dp[0]。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 101000
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
int f[N];
double dp[N];
int main()
{
int n,m,i,j;
while(cin>>n>>m)
{
if(!n&&!m) break;
memset(f,,sizeof(f));
memset(dp,,sizeof(dp));
int x,y;
for(i = ;i <=m ; i++ )
{
cin>>x>>y;
f[x] = y;
}
for(i = n- ; i >= ; i--)
{
if(f[i])
dp[i] += dp[f[i]];
else
{
for(j = ;j <= ; j++)
dp[i] += dp[i+j]*1.0/;
dp[i]+=;
}
}
printf("%.4f\n",dp[]);
}
return ;
}

第八题--ZOJ 3640 Help Me Escape (简单期望题)

这个题是d的战斗力值  也就是当战斗力为多少的时候可以确定一个终态 ,很显然当值为maxz+1 的时候 它最大可达2*maxz.

这样就可以写出递推方程 dp[i] = (dp[i+c[j]]+1)*1/n;(第j出口所需战斗力》=i) dp[i] += day[j] (第j出口所需战斗力<i)

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 20010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
int c[];
double dp[N];
int main()
{
int n,f,i,j;
while(cin>>n>>f)
{
memset(dp,,sizeof(dp));
for(i = ; i < n ;i++)
cin>>c[i];
sort(c,c+n);
for(i = *c[n-] ; i >= f ; i--)
{
int o = ,k=;
double t = ,tt=;
for(j = ; j < n ;j++)
{
if(i>c[j])
{
int d = (1.0+sqrt(5.0))/*c[j]*c[j];
t+=1.0/n*d;
}
else
{
k++;
if(c[j]==) o++;
else
t+=1.0/n*(dp[i+c[j]]+);
}
}
if(o&&fabs(-o*1.0/n)>eps)
dp[i] += (t+)/(-o*1.0/n);
dp[i] += t;
}
printf("%.3f\n",dp[f]);
}
return ;
}

H第九题--DU 4336 Card Collector(简单期望题)

状压一下,然后确定终态倒推。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 20010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
double dp[<<],p[];
int main()
{
int n,i,j,g;
while(scanf("%d",&n)!=EOF)
{
memset(dp,,sizeof(dp));
for(i = ;i < n; i++)
scanf("%lf",&p[i]);
for(j = (<<n)- ; j>= ; j--)
{
double t = ;
double o = ;
for(g = ; g < n ;g++)
if((<<g)&j) continue;
else
{
o+=p[g];
t+=p[g]*dp[j+(<<g)];
}
if(fabs(o)>eps)
dp[j] = (t+)/o;
}
printf("%f\n",dp[]);
}
return ;
}

第十题--SGU 495 Kids and Prizes(简单期望题)

正推题,这个题比较巧妙,可以确定初始态dp[1] = 1,因为第一个人拿到球的概率就为1,那么第i个拿到球的期望就为,他拿到球的概率*(dp[i-1]+1),他拿到球的概率就等于有球的房间/总房间

那么有球的房间就为n-dp[i-1],因为期望就为球数,所以dp[i-1]就为拿走的球数。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 100010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
double dp[N];
int main()
{
int i,n,m;
while(cin>>n>>m)
{
memset(dp,,sizeof(dp));
dp[] = ;
for(i = ; i <= m ;i++)
dp[i] = (dp[i-]+)*(-dp[i-]/n)+dp[i-]*dp[i-]/n;
printf("%.10f\n",dp[m]);
}
return ;
}

第十一题--ZOJ 3329 One Person Game(简单期望题)

也是比较好推的题目,相对前面来说会多一个未知数,但是推到最后就会发现只有一个未知数,一个方程一个未知数,可以求解。

可以把每一步的期望分为2部分保存,可以准确算出的用dp[i]表示 依旧是未知的用o[i]保存他的系数,留到最后求解。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 1010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
double dp[N],p[N],o[N];
int main()
{
int i,j,n,k1,k2,k3,g,a,b,c,t;
cin>>t;
while(t--)
{
memset(dp,,sizeof(dp));
memset(p,,sizeof(p));
memset(o,,sizeof(o));
cin>>n>>k1>>k2>>k3>>a>>b>>c;
int k = k1+k2+k3;
for(i = ; i <= k1 ; i++)
for(j = ;j <= k2 ; j++)
for(g = ; g <= k3 ; g++)
{
if(i==a&&j==b&&g==c) continue;
p[i+j+g]+=1.0/(k1*k2*k3);
}
for(i = n ; i >= ; i--)
{
for(j = ; j <= k ; j++)
{
dp[i]+=dp[i+j]*p[j];
o[i]+=p[j]*o[i+j];
}
dp[i]+=;
o[i]+=1.0/(k1*k2*k3);
}
if(fabs(-o[])>eps)
dp[] = dp[]/(-o[]);
printf("%.14f\n",dp[]);
}
return ;
}

第十二题--HDU 4652 Dice

有两种询问,一种一个推法,n个相同的话,dp[i]表示最后有连续i个相同的到最后有n个相同的点数的期望,dp[i] = 0,dp[i] = 1.0/m*dp[i+1]+1+(m-1)/m*dp[1];

另开一数组保存dp[1] 的系数,最后求解。

n个两辆不同,与之类似 dp[i] = ((m-i)*1.0/m*dp[i+1]+1)+1.0/m*dp[1]+1.0/m*dp[2]+....+1.0/m*dp[i]; 化简一下,每次可以消掉一个未知数,求到dp[1]的时候自然只剩了一个未知数。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 1000010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
double dp[N],o[N];
int main()
{
int i,t,n,m,k;
while(cin>>t)
{
while(t--)
{
memset(dp,,sizeof(dp));
memset(o,,sizeof(o));
scanf("%d%d%d",&k,&m,&n);
if(k==)
{
for(i = n- ; i >= ; i--)
{
dp[i] = 1.0/m*dp[i+]+;
o[i] = 1.0/m*o[i+]+(m-)*1.0/m;
}
dp[] = dp[]/(-o[]);
dp[] = dp[]+;
printf("%.12f\n",dp[]);
}
else
{
for(i = n- ;i >= ; i--)
{
dp[i] = ((m-i)*1.0/m*dp[i+]+)/(-(m-i)*1.0/m*o[i+]-1.0/m);
o[i] = ((m-i)*1.0/m*o[i+]+1.0/m)/(-(m-i)*1.0/m*o[i+]-1.0/m);
}
dp[] = dp[]+;
printf("%.12f\n",dp[]);
}
}
}
return ;
}

第十三题--HDU 4035 Maze(中等期望题)

树上求期望的题,其实也与之类似,仔细想下会发现叶子节点的期望状态比较好确定,因为它只有一个父亲节点所以这样写出来的方程会只有2个未知数,一个是父亲节点一个是1号节点,到最后父亲节点肯定只有1,所以又会变成一个方程一个未知数。

dp[i]表示第i节点到满足结果的期望。

i为叶子节点 dp[i] = p1i*dp[1]+p2i*dp[fa[i]]+p3i*exit(exit==0)

这样可以多开两个数组存两个未知数的系数。

i为非叶子节点 dp[i] = p1i*dp[1]+p2i*1/k*dp[v](v与i相连的节点,共有K个)+p3i*exit。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
using namespace std;
#define N 100010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
vector<int>ed[N];
double dp[N],p[N][];
double o[N][];
int flag;
void dfs(int u,int pre)
{
if(!flag) return ;
int i;
dp[u] = p[u][];
o[u][] = p[u][];
o[u][] = p[u][];
int k = ed[u].size();
double pp = ;
for(i = ; i < k ; i++)
{
int v = ed[u][i];
if(v==pre) continue;
dfs(v,u);
dp[u]+=p[u][]/k*dp[v];
o[u][]+=p[u][]/k*o[v][];
pp+=p[u][]/k*o[v][];
}
if(u==)
{
if(fabs(-(o[u][]+pp))>eps)
dp[u] = dp[u]/(-(o[u][]+pp));
else
flag = ;
return;
}
if(fabs(-pp)>eps)
{
dp[u] = (dp[u])/(-pp);
o[u][] = (o[u][])/(-pp);
o[u][] = p[u][]/k/(-pp);
}
else
{
flag = ;
return ;
}
}
int main()
{
int i,j,t,n;
int kk = ;
cin>>t;
while(t--)
{
memset(dp,,sizeof(dp));
memset(o,,sizeof(o));
scanf("%d",&n);
flag = ;
for(i = ;i <= n ;i++)
ed[i].clear();
for(i = ; i < n ;i++)
{
int u,v;
scanf("%d%d",&u,&v);
ed[u].push_back(v);
ed[v].push_back(u);
}
for(i = ; i <=n ;i++)
{
int x,y;
scanf("%d%d",&x,&y);
p[i][] = x/100.0;
p[i][] = y/100.0;
p[i][] = -p[i][]-p[i][];
}
dfs(,-);
printf("Case %d: ",++kk);
if(flag)
printf("%f\n",dp[]);
else
puts("impossible");
}
return ;

第十四题--HDU 4418 Time travel(高斯消元求期望)

这个题意吧有点难理解。。是这个时光机每次可以走1-m步 概率分别为p[i]。

为了好做,可以加n-2个点统一方向, 0 1 2 3 2 1

这样dp[i] = (dp[i+1]+1)*p[i+1]+(dp[i+2]+2)*p[i+2]+...(dp[i+m]+m)*p[i+m];

这样会发现无论你倒推还是正推都无法减少未知数,不过可以列出来n-2个方程,n-2个未知数,高斯消元。

需要先bfs出是否能够达到,然后保留能够达到的点。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 205
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
double p[N],a[N][N],ans[N];
int n,m,y,x,d,dis[N],g;
int zn;
bool vis[N];
void gauss(int zw,int zr)
{
int i,j,k,g = ;
for(k = ; k < zw && g < zr; k++,g++)
{
i = k;
for(j = k+ ; j <= zw ; j++)
{
if(fabs(a[j][g])>fabs(a[i][g]))
i = j;
}
if(fabs(a[i][g])<eps)
{
continue;
}
if(i!=k)
for(j = k ;j <= zr ; j++)
swap(a[i][j],a[k][j]);
for(i = k+ ; i <= zw ; i++)
{
if(fabs(a[i][k])<eps) continue;
double s = a[i][g]/a[k][g];
a[i][g] = 0.0;
for(j = g+ ; j <= zr; j++)
a[i][j] -= s*a[k][j];
}
}
for(i = zw ; i >= ; i--)
{
if(fabs(a[i][i])<eps) continue;
double s = a[i][zn];
for(j = i+ ; j <= zw ;j++)
s-=a[i][j]*ans[j];
ans[i] = s/a[i][i];
}
}
int bfs()
{
int i;
queue<int>q;
memset(vis,,sizeof(vis));
q.push(x);
vis[x] = ;
int ff = ;
while(!q.empty())
{
int u = q.front();
q.pop();
if(u==y||zn-u==y)
{
ff = ;
continue;
}
for(i = ; i <= g; i++)
{
int v = (u+dis[i])%zn;
if(!vis[v])
{
vis[v] = ;
q.push(v);
}
}
}
return ff;
}
int main()
{
int t,i,j;
cin>>t;
while(t--)
{
memset(a,,sizeof(a));
memset(ans,,sizeof(ans));
scanf("%d%d%d%d%d",&n,&m,&y,&x,&d);
zn = *n-;
g = ;
double sum = ;
for(i= ; i <= m; i++)
{
int pp;
scanf("%d",&pp);
if(pp>)
{
p[++g] = pp/100.0;
dis[g] = i;
sum+=p[g]*i;
}
}
if(d>)
x = zn-x;
if(x==y)
{
puts("0.00");
continue;
}
if(!bfs())
{
puts("Impossible !");
continue;
}
for(i = ; i < zn ; i++)
{
if(!vis[i]) continue;
a[i][i] = ;
if(i==y||y==zn-i) continue;
for(j = ; j <= g ;j++)
{
int dd = (dis[j]+i)%zn;
a[i][dd]-=p[j];
}
a[i][zn] += sum;
}
gauss(zn-,zn);
printf("%.2f\n",ans[x]);
}
return ;
}

第十五题--HDU 4089 Activation(中等概率题)

这个题因为会出现循环求所以有求期望的感觉。

分情况看一下 dp[i][j]表示队里有i个人 他在第j的位置到最终结果的概率。

j==1 dp[i][1] = p1*dp[i][1]+p2*dp[i][i]+p4.

k>=j>1 dp[i][j] = p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4;

j>k  dp[i][j] = p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1];

因为一个i循环里面只有一个dp[i][i]事未知的,可以开一个一维数组保存dp[i][j]里面还有dp[i][i]的系数。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 2010
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
double dp[N][N],o[N];
int main()
{
int i,j,n,m,k;
double p1,p2,p3,p4;
while(cin>>n>>m>>k)
{
scanf("%lf%lf%lf%lf",&p1,&p2,&p3,&p4);
memset(dp,,sizeof(dp));
memset(o,,sizeof(o));
int flag = ;
if(fabs(-p2-p1)<eps)
flag = ;
else
dp[][] = p4/(-p2-p1);
for(i = ;i <= n ;i++)
{
o[] = ;
for(j = ; j <= i; j++)
{
if(j<=k)
{
if(j==)
{
dp[i][j]+=p4;
o[j] = p2;
}
else
{
dp[i][j] += p4+p2*dp[i][j-]+p3*dp[i-][j-];
o[j] = p2*o[j-];
}
}
else
{
dp[i][j]+= p2*dp[i][j-]+p3*dp[i-][j-];
o[j] = p2*o[j-];
}
if(j==i)
{
if(fabs(-p1-o[j])<eps)
{
flag = ;
break;
}
dp[i][j] = dp[i][j]/(-p1-o[j]);
}
else
{
if(fabs(-p1-o[j])<eps)
{
flag = ;
break;
}
dp[i][j] = dp[i][j]/(-p1);
o[j] = o[j]/(-p1);
}
}
if(!flag) break;
for(j = ;j < i ;j++)
dp[i][j]+=dp[i][i]*o[j];
}
if(flag)
printf("%.5f\n",dp[n][m]);
else
printf("%.5f\n",0.0);
}
return ;
}

第十六题--ZOJ 3380 Patchouli's Spell Cards(中等题)

这题没有推出来。。。 组合题,

dp[i,j]  表示用前i个数字在m个里放了j个位置,这些数字不一定都有用到
概率dp专场   dp[i,j] = ∑ dp[i-1,j-k]*C[m-(j-k),k]          0≤k≤j , k<l
概率dp专场   最后答案为dp[n,m]

个人认为做法很棒。。

题解参照

 import java.text.*;
import java.io.*;
import java.util.*;
import java.math.*;
import java.applet.*;
public class Main
{
public static void main(String[] args)
{
Scanner cin = new Scanner(System.in);
BigInteger [][]dp = new BigInteger[][];
BigInteger o = BigInteger.valueOf();
BigInteger [][]c = new BigInteger[][];
int n,m,i,j,l,k;
for(i=;i<;i++)c[i][]=c[i][i]=BigInteger.valueOf();
for(i=;i<;i++){
for(j=;j<i;j++)
c[i][j]=c[i-][j-].add(c[i-][j]);
}
while(cin.hasNext())
{
m = cin.nextInt();
n = cin.nextInt();
l = cin.nextInt();
BigInteger s1 ,s2 = BigInteger.valueOf();
s1 = BigInteger.valueOf(n);
s1 = s1.pow(m);
if(l>m)
{
System.out.println("mukyu~");
continue;
}
else if(l>m/)
{
for(i=l;i<=m;i++)
{
s2=s2.add(c[m][i].multiply( BigInteger.valueOf(n-).pow(m-i) ));
}
s2=s2.multiply(BigInteger.valueOf(n));
}
else
{
for(i = ; i <= n ;i++)
for(j = ; j <= m; j++)
dp[i][j] = o;
dp[][] = BigInteger.ONE;
for(i = ; i <= n ;i++)
{
for(j = ; j <= m ;j++)
{
for(k = ; k <= Math.min(j, l-) ;k++)
dp[i][j] = dp[i][j].add(dp[i-][j-k].multiply(c[m-(j-k)][k]));
}
} s2 = dp[n][m];
s2 = s1.subtract(s2);
}
BigInteger gc = s2.gcd(s1);
System.out.println(s2.divide(gc)+"/"+s1.divide(gc));
}
}
}