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)
blank

相关推荐

  • 转换Cifar10数据集

    转换Cifar10数据集Cifar10数据集不讲了吧,入门必备,下载地址:https://www.cs.toronto.edu/~kriz/cifar.html官方提供三种形式的下载:可以看出是不提供图片形式的下载的,需要进行数据转换,虽然可以直接读成ndarray,但是对于初学者可能读图更直观点自己写了个转换程序(将bytes形式的文件转换为图片并分类存储):defrecover_cifar10(cifar10_

  • maven本地有包却加载失败_maven configuration problem

    maven本地有包却加载失败_maven configuration problem[INFO]BUILDFAILURE[ERROR]Failedtoexecute[ERROR]Formoreinformationabouttheerrorsandpossiblesolutions,pleasereadthefollowingarticles:1、问题情形项目代码是从SVN上刚下载的。同事在启动项目时,程序卡在下图这个地方不…

  • 汇编指令与机器码的相互转换(来自80×86汇编小站)「建议收藏」

    汇编指令与机器码的相互转换(来自80×86汇编小站)「建议收藏」作者:HSLY 网站:http://www.x86asm.com E-MAIL:pliceman_110@163.comHI,欢迎进入AssemblyLanguageintoMechineCode教程。首先你得从80×86汇编小站下载下载地址:Soft_Show.asp?SoftID=8  机器语言我们只要重点理解一下几个概念:    1.机器语言指令有

    2022年10月13日
  • 指令重排详解_cpu指令重排序

    指令重排详解_cpu指令重排序指令重排:编译器指令重排,cpu指令重排,内存指令重排。编译器可能会调整顺序,如下图,左边是c++源码,右边是优化后顺序一条汇编指令的执行是可以分为很多步骤的,分为不同的硬件执行取指IF译码和取寄存器操作数ID执行或者有效地址计算EX(ALU逻辑计算单元)存储器访问MEM写回WB(寄存器)指令重排只可能发生在毫无关系的指令之间,如果指令之间存在依赖关系,则不会重排。单线程内程序的执行结果不能被改变。1原子性是指一个操作是不可中断的.

    2022年10月17日
  • org.bson.codecs.configuration.CodecConfigurationException

    org.bson.codecs.configuration.CodecConfigurationException

  • vb学习什么[通俗易懂]

    vb学习什么[通俗易懂]学习几天的vb总结一下实在学习什么,我们看到的vb程序设计这本书中,第一句话就介绍了vb是什么,它是一门面向对象的可视化程序设计语言,而我们用的一个vb6.0其实是一个已经打包的平台,而在这门语言中提到了面向对象,那面向对象是什么,它就是书中提到的三要素:属性、事件、方法。属性是指对象的特征,描述对象的数据,在生活中可以理解为你看到一个人或者一个事物给你的外在表象,不同的事物具有…

发表回复

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

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