当前位置:首页 > 开发 > 编程语言 > 网络编程 > 正文

zoj 3822 Domination(dp)

发表于: 2014-10-13   作者:阿尔萨斯   来源:转载   浏览:
摘要: 题目链接:zoj 3822 Domination 题目大意:给定一个N∗M的棋盘,每次任选一个位置放置一枚棋子,直到每行每列上都至少有一枚棋子,问放置棋子个数的期望。 解题思路:大白书上概率那一张有一道类似的题目,但是因为时间比较久了,还是稍微想了一下。dp[i][j][k]表示i行j列上均有至少一枚棋子,并且消耗k步的概率(k≤i∗j),因为放置在i+1~n上等价与放在i+1行上,同理

题目链接:zoj 3822 Domination

题目大意:给定一个NM的棋盘,每次任选一个位置放置一枚棋子,直到每行每列上都至少有一枚棋子,问放置棋子个数的期望。

解题思路:大白书上概率那一张有一道类似的题目,但是因为时间比较久了,还是稍微想了一下。
dp[i][j][k]表示i行j列上均有至少一枚棋子,并且消耗k步的概率(kij),因为放置在i+1~n上等价与放在i+1行上,同理列也是如此。所以有转移方程:

  • dp[i][j][k+1]+=dp[i][j][k](nk)(Sk)
  • dp[i+1][j][k+1]+=dp[i][j][k](Ni)j(Sk)
  • dp[i][j+1][k+1]+=dp[i][j][k](Mj)i(Sk)
  • dp[i+1][j+1][k+1]+=dp[i][j][k](Ni)(Mj)(Sk)
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 55;
const int maxm = 2505;

int N, M;
double dp[maxn][maxn][maxm];

double solve () {
    int S = N * M;
    memset(dp, 0, sizeof(dp));
    dp[1][1][1] = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            int n = i * j;
            for (int k = max(i, j); k <= n; k++) {
                dp[i][j][k+1] += dp[i][j][k] * (n - k) / (S - k);
                dp[i+1][j][k+1] += dp[i][j][k] * (N - i) * j / (S - k);
                dp[i][j+1][k+1] += dp[i][j][k] * (M - j) * i / (S - k);
                dp[i+1][j+1][k+1] += dp[i][j][k] * (N - i) * (M - j) / (S - k);
            }
        }
    }

    /* for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { printf("%d %d:", i, j); for (int k = max(i, j); k <= i * j; k++) printf("%.3lf ", dp[i][j][k]); printf("\n"); } } */

    double ans = 0;
    for (int i = max(N, M); i <= S; i++)
        ans += (dp[N][M][i] - dp[N][M][i-1]) * i;
    return ans;
}

int main () {
    int cas;
    scanf("%d", &cas);
    while (scanf("%d%d", &N, &M) == 2) {
        printf("%.8lf\n", solve());
    }
    return 0;
}

zoj 3822 Domination(dp)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
Machine Time Limit: 2 Seconds Memory Limit: 65536 KB In a typical assembly line, machines are
Beautiful Meadow Time Limit: 5 Seconds Memory Limit: 32768 KB Tom's Meadow Tom has a meadow i
The Hive II Time Limit: 5 Seconds Memory Limit: 65536 KB There is a hive in the village. Like
From browsers to mobile phones, from tablets to tabletops, from industrial automation to the
Beautiful Meadow Time Limit: 5 Seconds Memory Limit: 32768 KB Tom's Meadow Tom has a meadow i
Tour in the Castle Time Limit: 5 Seconds Memory Limit: 32768 KB After the final BOSS is defea
The Hive II Time Limit: 5 Seconds Memory Limit: 65536 KB There is a hive in the village. Like
Tour in the Castle Time Limit: 5 Seconds Memory Limit: 32768 KB After the final BOSS is defea
链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2771 Get Out of the Glass
Mondriaan's Dream Problem Description Squares and rectangles fascinated the famous Dutch pain
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号