首先肯定要先把所有的关卡打通后去找两星几率最大的关卡刷星(论打游戏经验的重要性)。

所以从两星几率小的关打起,记录当前拿到x个星星的几率和当前走过的期望步数,如果发现剩下的关必须全两星,就直接计算答案。

因为期望的线性,所以直接加起来不会有什么问题。

#include<bits/stdc++.h>
#define double long double
using namespace std;
const int N = 4005;
int n,m;
double x[N],y[N];
int p[N];
bool cmp(int xx,int xy)
{
return y[xx]<y[xy];
}
double b[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%Lf%Lf",&x[i],&y[i]);
x[i]/=1000;y[i]/=1000;
}
for(int i=1;i<=n;i++)p[i]=i;
sort(p+1,p+n+1,cmp);
b[0]=1;
double ans=0;
double now=1;
for(int i=1;i<=n;i++)
{
int t=p[i];
if(m-(n-i+1)*2>=i-1)
{
double tmp=0;
for(int j=i;j<=n;j++)
{
tmp+=1/y[p[j]];
}
ans+=b[m-(n-i+1)*2]*tmp;
now-=b[m-(n-i+1)*2];
b[m-(n-i+1)*2]=0;
}
ans+=now/(x[t]+y[t]);
for(int j=2*n;j>=0;j--)
{
b[j]=0;
if(j>=1)b[j]=b[j-1]*x[t]/(x[t]+y[t]);
if(j>=2)b[j]+=b[j-2]*y[t]/(x[t]+y[t]);
}
}
printf("%.10Lf\n",ans);
return 0;
}

  

最新文章

  1. 使用 GitHub 和 Hexo 搭建个人独立博客
  2. 利用JS实现自定义滚动条
  3. git学习手册
  4. Java实现选择排序
  5. trie树---(插入、删除、查询字符串)
  6. PHP 获取服务器详细信息【转】
  7. C基础 北京大公司面试简单总结
  8. C#中实现对Excel特定文本的搜索
  9. (转)C++重写、重载和重定义的区别
  10. 获取Portal中POWL程序的APPLID
  11. 2018-03-03-解决win下凭据删除不干净而无法登录共项目录的问题
  12. Go学习——new()和 make()的区别详解(转载)
  13. 【java线程池】
  14. CommandLineRunner和ApplicationRunner的区别
  15. 浅谈awk命令
  16. sqlserver中 事物 索引及视图
  17. POJ 3905 Perfect Election (2-Sat)
  18. jquery checkbox相关 prop方法
  19. Linux下开发python django程序(Form表单对象创建和使用)
  20. struts2中两个action之间的跳转(struts.xml)

热门文章

  1. Oracle-归档日志详解(运行模式、分类)
  2. 20155308『网络对抗技术』Exp5 MSF基础应用
  3. 20155325 Exp7 网络欺诈防范
  4. navicat 创建查询失败 can not create file
  5. Java 多线程(三)之线程状态及其验证
  6. 设计模式 笔记 桥接模式 Bridge
  7. onSaveInstanceState和onRestoreInstanceState触发的时机
  8. WPF DataGrid列设置为TextBox控件的相关绑定
  9. Asp.Net_Session跟Cookie的记住登陆名
  10. 使用SignalR实时Web应用程序