首页 > 代码库 > ZOJ3822 ACM-ICPC 2014 亚洲区域赛牡丹江赛区现场赛D题Domination 概率DP(两种解法)
ZOJ3822 ACM-ICPC 2014 亚洲区域赛牡丹江赛区现场赛D题Domination 概率DP(两种解法)
题目地址:点击打开链接
这道题有两种做法,第一种是直接求期望,类似于poj 2096 区别在于这个步数有限。所以要迭代步数。
#include <cstdio> #include <cstring> #include <iostream> #define maxn 55//这里刚开始写成了50+10 那么maxn*maxn就会小很多wa了一次 using namespace std; double dp[maxn][maxn][maxn*maxn]; int N,M,T; int main() { while(~scanf("%d", &T))while(T--) { scanf("%d%d",&N,&M); memset(dp,0,sizeof(dp)); for(int i=N;i>=0;i--) for(int j=M;j>=0;j--) { if(i==N && j==M) continue;//状态定义:dp[i][j][k] 走了k步覆盖了i行j列,此情况下能完全覆盖的期望 for(int k=i*j;k>=max(i,j);k--)//步数不可能比i*j更多也要大于i,j中最大值因为已经覆盖了这么些 { double p0=1.0*(i*j-k)/(N*M-k); double p1=1.0*(M-j)*i/(N*M-k); double p2=1.0*(N-i)*j/(N*M-k); double p3=1.0*(N-i)*(M-j)/(N*M-k); dp[i][j][k]=dp[i][j][k+1]*p0+dp[i][j+1][k+1]*p1+dp[i+1][j][k+1]*p2+dp[i+1][j+1][k+1]*p3+1; } } printf("%.12lf\n",dp[0][0][0]); } return 0; }
第二种是求概率,完事以后再算期望。(若是对于不限步数的题目来说这个方法是不能用的)
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; double dp[55][55][55*55]; const double eps=1e-8; int main() { // freopen("in.txt","r",stdin); int t; cin>>t; while(t--) { int n,m; scanf("%d%d",&n,&m); memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); dp[1][1][1]=1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(i==n && j==m) break; for(int k=max(i,j);k<=i*j;k++) { dp[i][j][k+1]+=dp[i][j][k]*(i*j-k)/(n*m-k); dp[i+1][j][k+1]+=dp[i][j][k]*(n-i)*j/(n*m-k); dp[i][j+1][k+1]+=dp[i][j][k]*(m-j)*i/(n*m-k); dp[i+1][j+1][k+1]+=dp[i][j][k]*(n-i)*(m-j)/(n*m-k); } } } double sum=0; for(int i=max(n,m);i<=n*m;i++) sum+=dp[n][m][i]*i; printf("%.12f\n",sum); } return 0; }
ZOJ3822 ACM-ICPC 2014 亚洲区域赛牡丹江赛区现场赛D题Domination 概率DP(两种解法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。