首页 > 代码库 > ZOJ 3822 Domination
ZOJ 3822 Domination
dp :
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 51;
double dp[MAX*MAX][MAX][MAX];
int main() {
int cas;
int n,m;
scanf("%d",&cas);
while(cas--) {
scanf("%d %d",&n,&m);
memset(dp,0,sizeof(dp));
dp[0][0][0]=1.0;
double tot=n*m,res=0;
for(int i=1;i<=(n*m)-min(n,m)+1;i++) {
for(int j=1;j<=n;j++) {
for(int k=1;k<=m;k++) {
if(tot-i+1>0&&(n-(j-1))>0)
dp[i][j][k]+=dp[i-1][j-1][k]*(double)((n-(j-1))*k)/(double)(tot-i+1);
if(tot-i+1>0&&(m-k+1)>0)
dp[i][j][k]+=dp[i-1][j][k-1]*(double)(j*(m-k+1))/(double)(tot-i+1);
if((n-j+1)>0&&(m-k+1)>0&&(tot-i+1)>0)
dp[i][j][k]+=dp[i-1][j-1][k-1]*(double)((n-j+1)*(m-k+1))/(double)(tot-i+1);
if((tot-i+1)>0&&j*k-i+1>0)
dp[i][j][k]+=dp[i-1][j][k]*(double)(j*k-i+1)/(double)(tot-i+1);
}
}
// if(dp[i][n][m]!=0) printf("%d\n",i);
res+=(dp[i][n][m]-dp[i-1][n][m])*i;
}
printf("%.12lf\n",res);
}
return 0;
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 51;
double dp[MAX*MAX][MAX][MAX];
int main() {
int cas;
int n,m;
scanf("%d",&cas);
while(cas--) {
scanf("%d %d",&n,&m);
memset(dp,0,sizeof(dp));
dp[0][0][0]=1.0;
double tot=n*m,res=0;
for(int i=1;i<=(n*m)-min(n,m)+1;i++) {
for(int j=1;j<=n;j++) {
for(int k=1;k<=m;k++) {
if(tot-i+1>0&&(n-(j-1))>0)
dp[i][j][k]+=dp[i-1][j-1][k]*(double)((n-(j-1))*k)/(double)(tot-i+1);
if(tot-i+1>0&&(m-k+1)>0)
dp[i][j][k]+=dp[i-1][j][k-1]*(double)(j*(m-k+1))/(double)(tot-i+1);
if((n-j+1)>0&&(m-k+1)>0&&(tot-i+1)>0)
dp[i][j][k]+=dp[i-1][j-1][k-1]*(double)((n-j+1)*(m-k+1))/(double)(tot-i+1);
if((tot-i+1)>0&&j*k-i+1>0)
dp[i][j][k]+=dp[i-1][j][k]*(double)(j*k-i+1)/(double)(tot-i+1);
}
}
// if(dp[i][n][m]!=0) printf("%d\n",i);
res+=(dp[i][n][m]-dp[i-1][n][m])*i;
}
printf("%.12lf\n",res);
}
return 0;
}
ZOJ 3822 Domination
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。