HDU 3076:ssworld VS DDD(概率DP)
2024-10-18 00:07:20
http://acm.split.hdu.edu.cn/showproblem.php?pid=3076
ssworld VS DDD
Problem Description
One day, sssworld and DDD play games together, but there are some special rules in this games.
They both have their own HP. Each round they dice respectively and get the points P1 and P2 (1 <= P1, P2 <= 6). Small number who, whose HP to reduce 1, the same points will remain unchanged. If one of them becomes 0 HP, he loses.
As a result of technical differences between the two, each person has different probability of throwing 1, 2, 3, 4, 5, 6. So we couldn’t predict who the final winner.
They both have their own HP. Each round they dice respectively and get the points P1 and P2 (1 <= P1, P2 <= 6). Small number who, whose HP to reduce 1, the same points will remain unchanged. If one of them becomes 0 HP, he loses.
As a result of technical differences between the two, each person has different probability of throwing 1, 2, 3, 4, 5, 6. So we couldn’t predict who the final winner.
Input
There are multiple test cases.
For each case, the first line are two integer HP1, HP2 (1 <= HP1, HP2 <= 2000), said the first player sssworld’s HP and the second player DDD’s HP.
The next two lines each have six floating-point numbers per line. The jth number on the ith line means the the probability of the ith player gets point j. The input data ensures that the game always has an end.
For each case, the first line are two integer HP1, HP2 (1 <= HP1, HP2 <= 2000), said the first player sssworld’s HP and the second player DDD’s HP.
The next two lines each have six floating-point numbers per line. The jth number on the ith line means the the probability of the ith player gets point j. The input data ensures that the game always has an end.
Output
One float with six digits after point, indicate the probability sssworld won the game.
Sample Input
5 5
1.000 0.000 0.000 0.000 0.000 0.000
0.000 0.000 0.000 0.000 0.000 1.000
5 5
0.000 0.000 0.000 0.000 0.000 1.000
1.000 0.000 0.000 0.000 0.000 0.000
Sample Output
0.000000
1.000000
题意:两个人玩游戏,给出各自掷骰子得到不同点数的概率,点数小的扣一血,相同不扣血。
思路:概率DP,处理到第二个人血量剩余1的时候,然后再处理他降到0的时候的情况,不能直接循环第二个人血量为0的情况,即ans += dp[i][0] (1 <= i <= h1),因为这样的话dp[i][0]继承了dp[i+1][0]的状态,但是为0的时候游戏已经停止了,这样是不合理的。应该是ans += dp[i][1] * win / (1 - ave),这样的话才不会错,要注意考虑(1-ave)的情况,因为当前回合如果平局的话,下一个回合还是有机会赢的。(PS:很感谢ZLW师兄帮我debug了这题好久233)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const double eps = 0.00000001;
double d[][];
double dp[][]; int main()
{
int h1, h2;
while(~scanf("%d%d", &h2, &h1)) { //题目输入反了
double win = , lose = , ave = ;
for(int i = ; i < ; i++)
for(int j = ; j < ; j++)
scanf("%lf", &d[i][j]);
for(int i = ; i < ; i++) {
for(int j = ; j < ; j++) {
if(i == j) ave += d[][i] * d[][j];
else if(i < j) lose += d[][i] * d[][j];
else win += d[][i] * d[][j];
}
}
// printf("SIZE : %d\n", sizeof(dp));
double ans = ;
if(eps >= fabs( - ave)) {
printf("%.6f\n", ans);
continue;
}
for(int i = ; i <= h1+; i++)
for(int j = ; j <= h2+; j++)
dp[i][j] = ;
// dp[h1+1][h2-1] = dp[h1-1][h2+1] = dp[h1+1][h2] = dp[h1][h2+1] = 0;
dp[h1][h2] = ;
for(int i = h1; i >= ; i--) {
for(int j = h2; j >= ; j--) {
if(i == h1 && j == h2) continue;
dp[i][j] = (dp[i+][j] * lose + dp[i][j+] * win) / ((double) - ave);
}
}
for(int i = ; i <= h1; i++)
ans += dp[i][] * win / ((double) - ave);
printf("%.6f\n", ans);
}
return ;
}
最新文章
- layout优化实践
- [转]ActionScript 3.0入门:Hello World、文件读写、数据存储(SharedObject)、与JS互调
- LeetCode(7) - Reverse Integer
- 【Shell脚本学习1】Shell简介:什么是Shell,Shell命令的两种执行方式
- ActiveMQ之 TCP通讯机制
- 一个用python实现的东方时尚(驾校)抢课程序
- .NET页面301跳转处理
- 黄聪:Microsoft Enterprise Library 5.0 系列教程(三) Validation Application Block (初级)
- 从虚拟dom了解vue渲染函数
- 关于javascript中arguments的一个很好的例子
- 可遇不可求的Question之MySql4.0前版本不支持union与批量SQL提交
- stark组件的分页,模糊查询,批量删除
- 用Executors工具类创建线程池
- java 报错英文
- openstack rpc机制
- C - A Plug for UNIX (又是建图坑)
- python strip()
- php session的简单使用
- HDU1398 Square Coins(生成函数)
- Eclipse中快速 打出 main方法的签名