LightOJ 1030 【概率DP求期望】
2024-09-05 05:55:12
借鉴自:https://www.cnblogs.com/keyboarder-zsq/p/6216762.html 题意:n个格子,每个格子有一个值。从1开始,每次扔6个面的骰子,扔出几点就往前几步,然后把那个格子的金子拿走;
如果扔出的骰子+所在位置>n,就重新扔,直到在n;
问取走这些值的期望值是多少
解析:
【1】 【2】 【3】【4】 【5】 【6】 【7】 【8】 【9】
//格子和值都是一样,所以下述的话,值就是格子,格子就是值。。。
比如这样的9个格子,我们总底往上来
对于第9个格子,因为只有9,能取的期望就是9;
对于第8个格子,8是一定要取的,而9也是一定回取的,所以对于第8个格子,期望就是17;
对于第7个格子,7是一定要取的,对于后面可能是直接取了9,或者先取8再取9,情况是满足,对于每种情况概率是1/2,所以就是7+9/2+(8+9)/2=20;
PS:
上面的情况,在7后面的时候,我们可能取9,或者先取8,那么其实就是拿了第8个格子的期望和第9个格子期望,期望就是能取的值,然后*概率,全部情况的总和就是新的期望,有人会奇怪那7呢?我们的前提是对于第7格一定拿7啊;
对于第6个格子,那么就是6一定要拿的,然后会拿7,拿8,拿9,他们的期望*概率的总和+他能取的值就是6的第6个格子的期望;
...以此类推;
对于概率的其实一想更简单...
我们一开始就在1,概率就是1,然后扔一个骰子对于每个面的概率就是1/6,那么dp[i]代表概率,每次对能到达的地方更新概率,最后期望就是值乘以概率的总和+1,1是一定要取的哦~ 从后往前推
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.Vector; public class Main {
public static void main(String[] args) {
final int maxn = 10010;
Scanner cin = new Scanner(System.in);
int T = cin.nextInt();
int cnt = 0;
while(T-- != 0)
{
double[] dp = new double[maxn];
int n = cin.nextInt();
for(int i=1;i<=n;i++)
dp[i] = cin.nextDouble();
for(int i=n-1;i>=1;i--)
{
int k = Math.min(6, n-i);
for(int j=i+1;j<=i+k;j++)
{
dp[i] += dp[j]/(double)k;
}
}
System.out.printf("Case %d: %.10f\n",++cnt,dp[1]);
} }
}
最新文章
- Anciroid的IPC机制-Binder概述
- Bus Hound 的使用方法
- jQuery中的checkbox问题
- PDP 有多种定义,具体哪一种还需研究!!!!
- ubuntu12.04之后该死的文件关联
- adb 选择设备
- 第 5 章 工厂方法模式【Factory Method Pattern】
- EL表达式使用之类switch语句
- [置顶] javascript-基于对象or面向对象?
- 直接用request.setAttribute()会报错,在这之前应该先让request获取ServletActionContext.getRequest();方法 // request.getAttribute同理
- kali系统安装
- 验证表格多行某一input是否为空
- Linux定时器工具-crontab 各參数具体解释及怎样查看日志记录
- 利用tornado实现表格文件预览
- python爬虫之静态网页——全国空气质量指数(AQI)爬取
- Url的拦截问题
- Centos7下用户登录失败N次后锁定用户禁止登陆的方法
- HAProxy基础
- python 2 字典的基本使用
- Effective Java 第三版——75. 在详细信息中包含失败捕获信息
热门文章
- ftrace利器之trace-cmd和kernelshark
- Tensorflow[源码安装时bazel行为解析]
- Matplotlib 简单图例
- C#实现.Net对邮件进行DKIM签名和验证,支持附件,发送邮件签名后直接投递到对方服务器(无需己方邮件服务器)
- BugkuCTF SQL注入1
- Mysql优化系列(1)--Innodb重要参数优化
- Command Analyze failed with a nonzero exit code
- 牛客训练赛25-A-最长区间
- 读书笔记(chapter17)
- AAPT2 error: check logs for details 问题的终究修复