首页 > 代码库 > UVA542 - France '98(dp)
UVA542 - France '98(dp)
UVA542 - France ‘98(dp)
题目链接
题目大意:之前题目意思还以为看懂了,其实没看明白,它已经把各个选手分在各自所在的区域里面,这就意味着第一次的PK的分组已经确定,而且冠军必须是从两个左右分区出来的胜利者才有机会pk冠军。
解题思路:那么从1-16这个大的区间内诞生出来的冠军可能是来自左边,也可能是右边,然后再左边右边的子区间递归找出冠军。f[i][l][r]表示l-r这个区间的胜利者是i的概率,那么假设i在区间的最左边,f[i][l][r] = Sum(f[i][l][m]? f[k][m + 1][r] ? P[i][k]) (k属于[m+1, r]).要求i获胜那么左半边的冠军确定的,但是右半边的冠军未定。并且要乘上i打败k的概率p。情况在右半边类似。
代码:
#include <cstdio>
#include <cstring>
#include <cmath>
const int maxn = 16;
char name[maxn][maxn];
double p[maxn][maxn];
double f[maxn][maxn][maxn];
double esp = 1e-9;
void init () {
for (int i = 0; i < maxn; i++)
for (int j = 0; j < maxn; j++)
for (int k = 0; k < maxn; k++)
f[i][j][k] = -1.0;
}
double dp (int k, int l, int r) {
double& ans = f[k][l][r];
if (ans > 0)
return ans;
if (r - l == 1)
return ans = p[k][k == l?r:l];
int m = (l + r)>>1;
double tmp;
ans = 0;
if (k <= m) {
tmp = dp(k, l, m);
for (int i = m + 1; i <= r; i++)
ans += p[k][i] * tmp * dp(i, m + 1, r);
} else {
tmp = dp(k, m + 1, r);
for (int i = l; i <= m; i++)
ans += p[k][i] * tmp * dp(i, l, m);
}
return ans;
}
int main () {
while (scanf ("%s", name[0]) != EOF) {
for (int i = 1; i < maxn; i++)
scanf ("%s", name[i]);
int P;
for (int i = 0; i < maxn; i++)
for (int j = 0; j < maxn; j++) {
scanf ("%d", &P);
p[i][j] = P/100.0;
}
init();
for (int i = 0; i < maxn; i++)
printf ("%-10s p=%.2lf%\n", name[i], dp(i, 0, maxn - 1) * 100.0);
}
return 0;
}
UVA542 - France '98(dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。