[Poj3744]Scout YYF I (概率dp + 矩阵乘法)
2024-09-08 06:08:22
Scout YYF I
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 9552 | Accepted: 2793 |
Description
YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy's base. After overcoming a series difficulties, YYF is now at the start of enemy's famous "mine road". This is a very long road, on which there are numbers of mines. At first, YYF is at step one. For each step after that, YYF will walk one step with a probability of p, or jump two step with a probality of 1-p. Here is the task, given the place of each mine, please calculate the probality that YYF can go through the "mine road" safely.
Input
The input contains many test cases ended with EOF.
Each test case contains two lines.
The First line of each test case is N (1 ≤ N ≤ 10) and p (0.25 ≤ p ≤ 0.75) seperated by a single blank, standing for the number of mines and the probability to walk one step.
The Second line of each test case is N integer standing for the place of N mines. Each integer is in the range of [1, 100000000].
The First line of each test case is N (1 ≤ N ≤ 10) and p (0.25 ≤ p ≤ 0.75) seperated by a single blank, standing for the number of mines and the probability to walk one step.
The Second line of each test case is N integer standing for the place of N mines. Each integer is in the range of [1, 100000000].
Output
For each test case, output the probabilty in a single line with the precision to 7 digits after the decimal point.
Sample Input
0.5 0.5
Sample Output
0.5000000
0.2500000
分析:
概率dp是需要顺着推的,定义dp[i]表示到i的概率。当i有雷时,dp[i] = 0;
否则 dp[i] = dp[i - 1] * p + dp[i - 1] * (1 - p)
最后输出dp[dis[n] + 1]即行。
因为n很大,转移又固定,可以联想到矩乘 + 快速幂。于是就0MS过了
坑: 输入雷不一定有序,需要排序,精度输出需要%.7f 不能 %.7lf。
AC代码:
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
int n;
int dis[];
struct fi{
double data[][];
fi(){
for(int i = ;i < ;i++){
for(int j = ;j < ;j++){
data[i][j] = ;
}
}
}
}A,T,O;
inline fi operator *(fi A,fi B){
fi t;
for(int i = ;i < ;i++){
for(int j = ;j < ;j++){
for(int k = ;k < ;k++){
t.data[i][j] += A.data[i][k] * B.data[k][j];
}
}
}
return t;
}
fi cmd(fi C,int k){
fi D = O;
while(k){
if(k & )D = D * C;
k >>= ;
C = C * C;
}
return D;
}
double p;
int main(){
for(int i = ;i < ;i++)O.data[i][i] = 1.0;
while(~scanf("%d %lf",&n,&p)){
T.data[][] = (1.0 - p);
T.data[][] = p;
T.data[][] = 1.0;
T.data[][] = 0.0;
for(int i = ;i < ;i++){
for(int j = ;j < ;j++){
A.data[i][j] = 0.0;
}
}
A.data[][] = 1.0;
for(int i = ;i <= n;i++){
scanf("%d",&dis[i]);
}
sort(dis + ,dis + n + );
for(int i = ;i <= n;i++){
A = A * cmd(T,dis[i] - dis[i - ] - );
A.data[][] = ;
A = A * T;
}
printf("%.7f\n",A.data[][]);
}
}
最新文章
- 移动web资源整理
- Pycharm中使用GitHub
- SQL指令中一些特别值得注意的地方
- Teradata SQL tips
- Apache搭建多个站点方法详解
- SignalR的安装
- TOJ3651确定比赛名次
- Js 读写cookies
- Java_Hbase Timeout issue
- 8、Cocos2dx 3.0三,找一个小游戏开发3.0存储器管理的版本号
- CodeForces 620A Professor GukiZ&#39;s Robot
- synchronized关键字
- Java基础学习(五)&mdash;Collection
- java基础(十一章)
- install xdebug
- 智能合约开发环境搭建及Hello World合约
- EffictiveC++笔记 第2章
- CentOS 7 最小化安装配置以及网络服务器搭建、配置与管理
- ABAP其实也是挺好的语言
- post提交参数过多时,取消Tomcat对 post长度限制
热门文章
- Linux 从源码编译安装 Nginx
- sublime text3前端开发插件配置以及使用(个人喜爱)
- ftp 报错 200 Type set to A
- iOS猜拳游戏源码
- (四)docker创建私人仓库
- Python3简明教程(二)—— 变量和数据类型
- SQL分组聚合查询练习(SQL Server和Oracle相似)20190514
- url跳转路径参数获取
- Spring上传报错413
- react-native 在新版Xcode(10+)中运行出现的问题: node_modules/react-native/third-party/glog-0.3.4 , C compiler cannot create executables