zoj 3822 Domination(dp)

5881 단어
제목 링크: zoj 3822 Domination
제목 대의: N∗M의 바둑판을 정하고 매번 한 위치를 선택하여 바둑알을 하나씩 놓아라. 줄마다 적어도 한 개의 바둑알이 있을 때까지 바둑알을 놓아라. 바둑알의 개수에 대한 기대를 물어본다.
문제풀이 사고방식: 대백서에 있는 확률 한 장에 비슷한 문제가 하나 있는데 시간이 오래 걸려서 조금 생각해 봤어요.dp[i][j][k]는 i행 j열에 적어도 한 개의 바둑알이 있고 k보를 소모할 확률(k≤i∗j)을 나타낸다. i+1~n에 놓는 등가와 i+1행에 놓는 등가가 있기 때문에 같은 배열도 마찬가지다.그래서 전이 방정식이 있다.
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) 
#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("
"); } } */

    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
", solve());
    }
    return 0;
}
Angular에서 동적으로 구성 요소 생성
낙곡P3750 [6개 성 연합고사 2017] 이별은 축원 dp

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage