[Codeforces 865C]Gotta Go Fast(期望dp+二分答案)

题面

一个游戏一共有n个关卡,对于第i关,用a[i]时间通过的概率为p[i],用b[i]通过的时间为1-p[i],每通过一关后可以选择继续下一关或者时间清0并从第一关开始,先要求通过所有关卡的时间和不能超过R才算彻底通关,问直到彻底通关位置的游戏时间的期望值为多少

分析

二分从头开始通关的用时期望mid

设\(dp[i][j]\)表示通前i关,当前时间为j的期望,倒推期望.

若超时重新开始,则\(dp[i][j]=mid\)

若用方法a通过这一关,则更新j,\((dp[i+1][j+a[i]]+a[i])*p[i]\)

用方法b同理

总而言之,有$$dp[i][j]=min(mid,(dp[i+1][j+a[i]]+a[i])p[i],(dp[i+1][j+b[i]]+b[i])(1-p[i]))$$

如果最终答案\(dp[1][0]<mid\),就缩小二分范围,否则增大二分范围

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 50
#define maxv 5000
#define maxrb 1e10
#define maxt 150 //二分答案迭代次数,处理精度
using namespace std;
int n,r;
int a[maxn+5],b[maxn+5];
double p[maxn+5];
double dp[maxn+5][maxv+5];
//dp[i][j]第i关,用时j通关的期望
//二分从1关开始通完的期望mid
bool check(double mid){
for(int i=n;i>=1;i--){
for(int j=r+1;j<=maxv;j++){
dp[i+1][j]=mid;
//通关超过时间限制,回到起点重新开始
}
for(int j=0;j<=r;j++){
double t1=(dp[i+1][j+a[i]]+a[i])*p[i];
double t2=(dp[i+1][j+b[i]]+b[i])*(1-p[i]);
dp[i][j]=min(mid,t1+t2);
}
}
if(dp[1][0]<mid) return 1;//如果实际dp值比二分值更小,可以继续缩小二分范围
else return 0;
}
int main(){
scanf("%d %d",&n,&r);
for(int i=1;i<=n;i++){
scanf("%d %d",&a[i],&b[i]);
scanf("%lf",&p[i]);
p[i]/=100;
}
double lb=0,rb=1e10,mid,ans=0;
for(int i=1;i<=maxt;i++){
mid=(lb+rb)/2;
if(check(mid)){
ans=mid;
rb=mid;
}else lb=mid;
}
printf("%.9lf",ans);
}

最新文章

  1. 【xcode5的使用】
  2. 使用curl传递cookie错误的问题
  3. Windows Azure Virtual Machine (28) 使用Azure实例级别IP,Instance-Level Public IP Address (PIP)
  4. 时间同步出现ntpdate[1788]: the NTP socket is in use, exiting
  5. Inversion of Control Containers and the Dependency Injection pattern(转)
  6. selenium处理滚动条
  7. BZOJ-1834 网络扩容 最小费用最大流+最大流+乱搞
  8. 怎么使用PHP获取用户客户端真实IP的解决方案呢?
  9. 使用自定义《UIActivity》进行内容分享-b
  10. 转: 静态模式makefile中$(cobjs): $(obj)/%.o: $(src)/%.c
  11. WPF之Binding的使用
  12. cocos2d-x游戏开发系列教程-坦克大战游戏之虚拟手柄的显示
  13. TMCache
  14. Python的time和datetime模块
  15. IDEA设置生成带注释的getter和setter解决方案 (图文教程)
  16. SD 笔记01
  17. Helm - Kubernetes服务编排的利器
  18. Linux中各个文件的作用
  19. Internet spirit
  20. February 7th, 2018 Week 6th Wednesday

热门文章

  1. 行人重识别(ReID) ——基于Person_reID_baseline_pytorch修改业务流程
  2. ASE Beta Sprint - backend scrum 1
  3. Codeforces Round #421 (Div. 2) - B
  4. django中collectstatic的使用
  5. MacOS系統Flutter打包apk
  6. Java 根据银行卡号获取银行名称以及图标
  7. bootstrap模态框模板代码
  8. SQL Server数据库的软硬件性能瓶颈
  9. B/S大文件上传解决方案
  10. 配置自己的CocoaPods库