zoj 3822 Domination (可能性DP)

zoj 3822 Domination (可能性DP)

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

zoj 3822 Domination (可能性DP)此处内容已经被作者隐藏,请输入验证码查看内容
验证码:
请关注本站微信公众号,回复“”,获取验证码。在微信里搜索“”或者“”或者微信扫描右侧二维码都可以关注本站微信公众号。


Domination



Time Limit: 8 Seconds      
Memory Limit: 131072 KB      
Special Judge


Edward is the headmaster of Marjar University. He is enthusiastic about chess and often plays chess with his friends. What’s more, he bought a large decorative chessboard with N rows and Mcolumns.

Every day after work, Edward will place a chess piece on a random empty cell. A few days later, he found the chessboard was dominated by the chess pieces. That means there is at least one chess piece in every row. Also, there is at least one chess piece in every column.

“That’s interesting!” Edward said. He wants to know the expectation number of days to make an empty chessboard of N × M dominated. Please write a program to help him.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

There are only two integers N and M (1 <= NM <= 50).

Output

For each test case, output the expectation number of days.

Any solution with a relative or absolute error of at most 10-8 will be accepted.

Sample Input

2
1 3
2 2

Sample Output

3.000000000000
2.666666666667

题意:向一个N*M的棋盘里随机放棋子,每天往一个格子里放一个。求每一行每一列都有棋子覆盖的天数。

思路:开一个三维数组,dp[i][j][k]:有i行j列被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]*i*(m-j)/(n*m-k);        

//添加一个棋子,多覆盖一列

dp[i+1][j+1][k+1]=dp[i][j][k]*(n-i)*(m-j)/(n*m-k);  

//添加一个棋子,多覆盖一行及一列

dp[i][j][k+1]=dp[i][j][k]*(i*j-k)/(n*m-k);    

//添加一个棋子,行、列数没有添加

则ans=dp[n][m][k]*k,(k=0…n*m). //当i==n&&j==m时特殊处理,最后一项去掉。

易知dp[0][0][0]=1;

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 55
#define LL __int64
const int inf=0x1f1f1f1f;
const double eps=1e-10;
double dp[N][N][N*N];
int n,m;
void inti()
{
    int i,j,k;
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=m;j++)
        {
            for(k=0;k<=n*m;k++)
                dp[i][j][k]=0;
        }
    }
}
int main()
{
    int i,j,k,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        inti();
        dp[0][0][0]=1;
        int tt=n*m;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                for(k=0;k<=n*m;k++)
                {
                    if(i==n&&j==m)
                        dp[i][j][k]=(dp[i-1][j][k-1]*(n-i+1)*j+dp[i][j-1][k-1]*i*(m-j+1)+dp[i-1][j-1][k-1]*(n-i+1)*(m-j+1))/(tt-k+1);
                    else
                        dp[i][j][k]=(dp[i-1][j][k-1]*(n-i+1)*j+dp[i][j-1][k-1]*i*(m-j+1)+dp[i-1][j-1][k-1]*(n-i+1)*(m-j+1)+dp[i][j][k-1]*(i*j-k+1))/(tt-k+1);
                }
            }
        }
        double ans=0;
        for(i=0;i<=tt;i++)
            ans+=dp[n][m][i]*i;
        printf("%.9f\n",ans);
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117891.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • react路由跳转

    react路由跳转React中几种页面跳转方式1、使用react-router-dom中的Link实现页面跳转一般适用于,点击按钮或其他组件进行页面跳转,具体使用方式如下:<Linkto={{pathname:’/path/newpath’,state:{//页面跳转要传递的数据,如下data1:{},data2:[]},}}><Butt

  • 国外推荐:计算机专业人士必读的书籍_计算机专业排名世界

    国外推荐:计算机专业人士必读的书籍_计算机专业排名世界国外大牛推荐:计算机专业人士必读好书(30本经典)分类:程序人生2014-04-1123:17175人阅读评论(0)收藏举报计算机书籍1.《代码大全》史蒂夫·迈克康奈尔  推荐数:1684  “优秀的编程实践的百科全书,《代码大全》注重个人技术,其中所有东西加起来,就是我们本能所说的“编写整洁的代码”。这本书有50

  • JS合并数组对象中重复数据[通俗易懂]

    JS合并数组对象中重复数据[通俗易懂]数组重组数据源数据:目标数据://源数据varoldData=[{city_id:1,city_name:’北京’,city_img:”http://dfknbdjknvkjsfnvlkjdn.png”,city_country:”中国”},{city_id:2,city_name:’上海’,city_img:”http://wergerbe.png”,city_country

    2022年10月30日
  • 开放API接口_软件接口开放

    开放API接口_软件接口开放前言在开发测试阶段,或者是在写Demo的时候,难免会用到一些测试数据,有时苦于没有可用的接口,需要自己动手去写,但是这样大大降低了效率,前期我也找了一些开放的接口,这篇文章整理一下,以下接口完全免费,不用注册,返回格式全是JSON,所有接口均可无限制使用,有需要的小伙伴可以进来看看。(ps:所有数据来源于网络,如有侵权,请作者联系删除)图片类接口美女图片:https://w…

  • 阿拉伯媒体爆百度被黑最新进展 疑似一伊朗少年所为

    阿拉伯媒体爆百度被黑最新进展 疑似一伊朗少年所为

  • 模型融合stacking实战

    模型融合stacking的原理具体不再解释,有的博客已经解释很清楚了,还是附一张经典图吧,直接上完整程序(根据后面的数据集下载地址可以下载数据集,然后直接运行程序):#Loadinourlibrariesimportpandasaspdimportnumpyasnpimportreimportxgboostasxgbimportwarningswa…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号