51nod 1450 闯关游戏_51nod1450闯关游戏-程序员宅基地

一个游戏App由N个小游戏（关卡）构成，将其标记为0,1,2，..N-1。这些小游戏没有相互制约的性质，玩家可以任意时刻玩任意一个小游戏，且每个小游戏可以玩任意多次，一个小游戏玩一次消耗玩家恰好1min的时间。每个小游戏会根据玩家的表现返回3种结果：1）挑战失败；2）挑战成功并获得1颗星；3）挑战成功且获得2颗星。玩家可以多次挑战同一个小游戏，而且系统会记录玩家多次挑战中的最好成绩。（注意：两颗星优于一颗星优于挑战失败。）
这个游戏App通关需要同时满足2个条件：1）N个小游戏的系统记录的最好成绩都是成功；2）这N个小游戏的系统记录成绩中的星星总数至少是M颗。
根据一些统计，一个玩家在任一次玩第i个小游戏时，都会独立的发生以下结果：
* 有（1000 - X[i] - Y[i]）*0.001的概率会挑战失败；
* 有 X[i]*0.001 的概率会挑战成功并获得一颗星；
* 有 Y[i]*0.001 的概率会挑战成功并获得两颗星.
其中1<=X[i],Y[i],且X[i]+Y[i]<=1000,且都为整数.
问一个玩家从安装完这个游戏App到这个游戏App通关，最优策略下需要花费时间的期望E。输出E的值，以min为该时间单位。（误差在1e-7内）

例如：样例中有两个小游戏，且两个小游戏每次玩必能通过，且有0.5的概率拿两颗星。玩家可以先各玩一个小游戏一次，有0.75的概率能拿至少3颗星；有0.25的概率只能拿2颗星，此时需要盯着一关不停的玩，直到得到两颗星，这需要1/2 * 1 + 1/4 * 2 + 1/8 * 3 + ... + 1/(2^k) * k + .... 次。所以，E = 0.75*2 + 0.25*（2 + 1/2 * 1 + 1/4 * 2 + 1/8 * 3 + ... + 1/(2^k) * k + .... ）= 2.5。

Input

第一行两个个整数N，M，且1<=N<=2000，N <= M <= 2N
接下来N行，每行两个整数,X[i]、Y[i]，其中1<=X[i],Y[i],且X[i]+Y[i]<=1000

Output

一个浮点数，即期望E。确保E的精度与正解的绝对误差或相对误差小于1e-7。

Input示例

2 3
500 500
500 500

Output示例

2.5

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

期望DP~

啊♂，拖了一天，结果还是抄了尹神的呢。

我们先把m-=n，表示至少有m个是两颗星

用f[i][j]表示还有i个没有挑战过，还有j个必须是2颗星的期望，那么我们分开更新即可。

但是照这种更新方式的话，完全不需要排序使得后面的m个必须是2颗星啊。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int n,m,k;
double f[2001][2001];

struct node{
	double x,y;
	bool operator < (const node&u)
	{
		return y<u.y;
	}
}a[2001];

int main()
{
	scanf("%d%d",&n,&m);m-=n;
	for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
	sort(a+1,a+n+1);
	for(int i=0;i<m;i++) f[n][i]=999999999;
	for(int i=n-1;~i;i--)
	{
		for(int j=0;j<m;j++)
		  f[i][j]=min(
		  1000/(a[i+1].x+a[i+1].y)+a[i+1].x/(a[i+1].x+a[i+1].y)*f[i+1][j]
		  +a[i+1].y/(a[i+1].x+a[i+1].y)*f[i+1][j+1],
		  1000/a[i+1].y+f[i+1][j+1]);
		f[i][m]=1000/(a[i+1].x+a[i+1].y)+f[i+1][m];
	}
	printf("%.8lf\n",f[0][0]);
	return 0;
}

本文链接：https://blog.csdn.net/SenyeLicone/article/details/74852974

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

基于单片机12864的出租车计价器设计-程序员宅基地

文章浏览阅读1.2k次，点赞10次，收藏13次。*单片机设计介绍，基于单片机12864的出租车计价器设计。

从零开始搭建一个GIS开发小框架（一）——基本框架_greatmaps-程序员宅基地

文章浏览阅读2.7k次，点赞2次，收藏33次。使用GMap.Net控件从零开始搭建一个GIS开发小框架_greatmaps

c++ 泛型编程/提高编程/c++入门_c++泛型编程编译-程序员宅基地

文章浏览阅读344次。模板就是建立通用的模具，大大提高复用性。_c++泛型编程编译

7 重载自增和自减运算符-程序员宅基地

文章浏览阅读477次，点赞14次，收藏4次。运算符重载实际上是一种特殊形式的C++多态。重载运算符时，需要用到被称为运算符函数的特殊函数形式。运算符函数的函数名比较特殊，可以认为是operator关键字和运算符的组合。运算符函数也是一个函数，具有形参和返回值。运算符函数的定义如下：返回类型 operator 运算符符号(参数列表)函数体。_重载自增

经典入门 | 高级转录组分析和R数据可视化-程序员宅基地

文章浏览阅读120次。福利公告：为了响应学员的学习需求，经过易生信培训团队的讨论筹备，现安排《高级转录组分析和R数据可视化》于2023年12月15-17线上/线下课程 (线上课是通过腾讯会议实时直播线下课，实时互动，并录制有视频回放，无限期观看)。报名参加线上直播课的老师可在365天内选择参加同课程的一次线下课。期待和大家的线上线下相识。相关课程转录组线上/线下开课时间：2023/12/15-2023/12/17临床..._高级生信可视化图

linux输入多行内容至文件_linux写入多行内容到文件-程序员宅基地

文章浏览阅读4.9k次，点赞4次，收藏11次。linux输入多行内容至文件1. 单行写入[root@cn01 test]# echo "192.168.1.1" >test.txt[root@cn01 test]# cat test.txt 192.168.1.12. 单行追加[root@cn01 test]# echo "192.168.1.1" >>test.txt[root@cn01 test]# cat test.txt 192.168.1.1192.168.1.13. 多行写入[root@cn01 _linux写入多行内容到文件

随便推点

unity-shader（中级）_lightmode" shader-程序员宅基地

文章浏览阅读1.6k次，点赞2次，收藏5次。与深度测试，透明度测试类似，决定一个片元是否被扔掉。深度测试的比较数据在深度缓冲中，透明度测试的比较对象是颜色缓冲中的值，而模版测试的比较数据在Stencil中，并且模板测试要先于深度测试与透明度测试，在fragment函数之前就会执行模板测试。参数描述Ref就是参考值，当参数允许赋值时，会把参考值赋给当前像素ReadMask对当前参考值和已有值进行mask操作，默认值255，一般不用WriteMask写入Mask操作，默认值255，一般不用Comp比较方法。CompAlways。......_lightmode" shader