51nod 1450 闯关游戏
2024-10-15 21:10:07
首先肯定要先把所有的关卡打通后去找两星几率最大的关卡刷星(论打游戏经验的重要性)。
所以从两星几率小的关打起,记录当前拿到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;
}
最新文章
- 使用 GitHub 和 Hexo 搭建个人独立博客
- 利用JS实现自定义滚动条
- git学习手册
- Java实现选择排序
- trie树---(插入、删除、查询字符串)
- PHP 获取服务器详细信息【转】
- C基础 北京大公司面试简单总结
- C#中实现对Excel特定文本的搜索
- (转)C++重写、重载和重定义的区别
- 获取Portal中POWL程序的APPLID
- 2018-03-03-解决win下凭据删除不干净而无法登录共项目录的问题
- Go学习——new()和 make()的区别详解(转载)
- 【java线程池】
- CommandLineRunner和ApplicationRunner的区别
- 浅谈awk命令
- sqlserver中 事物 索引及视图
- POJ 3905 Perfect Election (2-Sat)
- jquery checkbox相关 prop方法
- Linux下开发python django程序(Form表单对象创建和使用)
- struts2中两个action之间的跳转(struts.xml)