现在的位置: 首页 > 综合 > 正文

POJ 3071 Football(区间DP)

2019年02月11日 ⁄ 综合 ⁄ 共 776字 ⁄ 字号 评论关闭

递推过程中应该考虑的是比赛的层数,比如这样:


[盗图...]


第i个人在第k层比赛获胜的概率:dpki = ∑(dp(k - 1)i * dp(k - 1)j * pij)。


但是如何判断第i个人和第j个在第k层相遇是否合法呢,即是否在同一个子树中?

这篇博客的方法很巧妙:POJ 3071 Football(概率问题) - 窝不是爱酱,喵~~~~ - 博客频道 - CSDN.NET

在第k层比赛的选手,编号(从0开始)写作二进制的第k位不会相同。

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
using namespace std;
#define MAXN (1 << 7) + 10

int n;
double p[MAXN][130], dp[MAXN][MAXN];

int main()
{
//    freopen("3071.in", "r", stdin);

    while(scanf("%d", &n) && n != -1)
    {
        int tot = (1 << n);
        for(int i = 0; i < tot; i++)
            for(int j = 0; j < tot; j++)
                scanf("%lf", &p[i][j]);

        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < tot; i++)
            dp[0][i] = 1;

        for(int k = 1; k <= n; k++)
            for(int i = 0; i < tot; i++)
                for(int j = 0; j < tot; j++)
                    if(((j >> (k - 1) ) ^ 1) == (i >> (k - 1)))
                        dp[k][i] += dp[k - 1][i] * dp[k - 1][j] * p[i][j];
        int ans = 0;
        for(int i = 0; i < tot; i++)
            if(dp[n][i] > dp[n][ans])
                ans = i;
        printf("%d\n", ans + 1);
    }
    return 0;
}

抱歉!评论已关闭.