刷题总结——Aeroplane chess(hdu4405)
2024-09-02 11:15:00
题目:
Problem Description
Hzz loves aeroplane chess very much. The chess map contains N+1 grids labeled from 0 to N. Hzz starts at grid 0. For each step he throws a dice(a dice have six faces with equal probability to face up and the numbers on the faces are 1,2,3,4,5,6). When Hzz is at grid i and the dice number is x, he will moves to grid i+x. Hzz finishes the game when i+x is equal to or greater than N.
There are also M flight lines on the chess map. The i-th flight line can help Hzz fly from grid Xi to Yi (0<Xi<Yi<=N) without throwing the dice. If there is another flight line from Yi, Hzz can take the flight line continuously. It is granted that there is no two or more flight lines start from the same grid.
Please help Hzz calculate the expected dice throwing times to finish the game.
Input
There are multiple test cases.
Each test case contains several lines.
The first line contains two integers N(1≤N≤100000) and M(0≤M≤1000).
Then M lines follow, each line contains two integers Xi,Yi(1≤Xi<Yi≤N).
The input end with N=0, M=0.
Each test case contains several lines.
The first line contains two integers N(1≤N≤100000) and M(0≤M≤1000).
Then M lines follow, each line contains two integers Xi,Yi(1≤Xi<Yi≤N).
The input end with N=0, M=0.
Output
For each test case in the input, you should output a line indicating the expected dice throwing times. Output should be rounded to 4 digits after decimal point.
Sample Input
2 0
8 3
2 4
4 5
7 8
0 0
8 3
2 4
4 5
7 8
0 0
Sample Output
1.1667 2.3441
题解:
期望dpsb题···不多说了
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+;
double f[N];
int n,m,to[N];
inline int R(){
char c;int f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f;
}
int main(){
//freopen("a.in","r",stdin);
while(scanf("%d%d",&n,&m)){
if(n==&&m==) break;
memset(to,,sizeof(to));memset(f,,sizeof(f));int a,b;
for(int i=;i<=m;i++) a=R(),b=R(),to[a]=b;
for(int i=n-;i>=;i--){
if(to[i]){
f[i]=f[to[i]];continue;
}
for(int j=;j<=;j++)
f[i]+=(f[i+j]+)/;
}
printf("%0.4f\n",f[]);
}
return ;
}
最新文章
- tkinter事件机制
- dpctl 工具使用
- [DNS][转]EDNS
- javascript 利用匿名函数对象给你异步回调方法传参数
- EmguCV+Win7+Visual C# 2012 配置
- 探秘Java中String、StringBuilder以及StringBuffer
- document.body为null的问题
- access to modified closure 闭包的问题
- .h头文件 .lib库文件 .dll动态库文件之间的关系
- 关于arguments.callee的用途
- centeros resin安装脚本启动
- 使用MIDAS访问远程Access数据库
- 浅谈JavaScript中继承的实现
- Servlet之文件的上传与下载
- 异常详细信息: Abp.AbpException: No language defined!
- 项目实战7—Mysql实现企业级数据库主从复制架构实战
- 【Git】Git工具常用命令
- java笔记----获取项目resource中class下的路径
- LeetCode算法题-Student Attendance Record I(Java实现)
- 第九章:Servlet工作原理解析