[CF739E]Gosha is hunting

news/2024/4/24 4:37:51/

codeforces

description

你的面前有\(n\)只迪莫,你有\(A\)个大师球和\(B\)个国王球可以用来捕捉这些迪莫。
用大师球捕捉第\(i\)只迪莫的成功概率是\(u_i\),用国王球捕捉第\(i\)只迪莫的成功概率是\(v_i\)
(不过好像国王球的捕捉成功概率是100%?)
对于每一只迪莫,你不可以使用同种咕噜球超过一次,但你可以同时使用大师球和国王球,两种都成功了的话只算捕捉到一只迪莫。
求你在期望意义下最多可以捕捉到多少只迪莫。
\(n \le 2000,0 \le A,B \le n\)

sol

有一个\(O(n^3)\)\(dp\):设\(f_{i,j,k}\)表示前\(i\)只迪莫,使用了\(j\)个大师球和\(k\)个国王球的答案。
转移的话直接枚举第\(i\)只迪莫的捕捉方式即可。
然后
直接凸优化套凸优化就可以做到\(O(n\log^2w)\)了。

code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 2005;
const double eps = 1e-8;
struct info{double f;int a,b;bool operator < (const info &x) const{if (f!=x.f) return f<x.f;if (b!=x.b) return b>x.b;return a>x.a;}info operator + (const info &x) const{return (info){f+x.f,a+x.a,b+x.b};}
}dp[N];
int n,A,B;double u[N],v[N];
inline void upt(info &x,info y){if (x<y) x=y;}
void solve(double ca,double cb){dp[0]=(info){0,0,0};for (int i=1;i<=n;++i){dp[i]=dp[i-1];upt(dp[i],dp[i-1]+(info){u[i]-ca,1,0});upt(dp[i],dp[i-1]+(info){v[i]-cb,0,1});upt(dp[i],dp[i-1]+(info){u[i]+v[i]-u[i]*v[i]-ca-cb,1,1});}
}
int main(){scanf("%d%d%d",&n,&A,&B);for (int i=1;i<=n;++i) scanf("%lf",&u[i]);for (int i=1;i<=n;++i) scanf("%lf",&v[i]);double L=0,R=1,l,r,M,m;while (R-L>eps){M=(L+R)/2;l=0;r=1;while (r-l>eps){m=(l+r)/2;solve(M,m);if (dp[n].b<=B) r=m;else l=m;}solve(M,r);if (dp[n].a<=A) R=M;else L=M;}solve(R,r);printf("%.4lf\n",dp[n].f+R*A+r*B);return 0;
}

转载于:https://www.cnblogs.com/zhoushuyu/p/9428927.html


http://www.ppmy.cn/news/922051.html

相关文章

下岗职工_下岗后我如何获得多位软件工程师的面试

下岗职工 “Opportunities to find our deeper powers come when life seems most challenging.” -Joseph Campbell “当生活似乎最具挑战性时&#xff0c;就有机会找到我们更深层的力量。” 约瑟夫坎贝尔 I was recently laid off for the first time in my life. I realized…

2019长沙理工第十四届程序设计竞赛

我们十分荣幸的有机会作为邀请队伍去了长沙理工大学参加他们的第十四届程序设计竞赛现场赛&#xff0c;在这里感谢长沙理工的同学们~ 这是我们队伍第一次团队比一次比较正规的比赛吧&#xff08;之前的队伍拆了&#xff09;。总的来说发挥的一般般&#xff0c;就A了6个题&…

行为型模式 11 访问者模式

访问者模式Visitor 表示一个作用于某对象结构中的各元素的操作&#xff0c;它使你可以在不改变各元素的类的前提下定义作用于这些元素的新操作。 有某个操作&#xff0c;它是作用于一些元素之上的&#xff0c;而这些元素属于某一个对象结构。 Visitor&#xff1a;抽象访问者&…

知识是如何进行跨学科流通的?

Neri Oxman 被业界认为是 “全球最大胆的跨学科思想家” Neri解释克式循环创意图谱&#xff08;KCC&#xff09; 节选自奈飞纪录片《抽象》 “我不认为时尚只是时尚&#xff0c;生物只是生物。就像我从不把建筑、设计、文化分割对待。” —— Neri Oxman 译者注 上一期我们提…

再生医学“独角兽”Orca Bio同时获得先进疗法和孤儿药称号,改善异体干细胞移植患者预后-1

成功获得 1.92 亿美元的 D 轮融资和 “独角兽” 身份后的几个月后&#xff0c;今日&#xff0c;美国生命科学公司 Orca Bio&#xff08;以下简称“Orca”&#xff09;再一次“大获全胜”。 Orca Bio 凭借其治疗血液干细胞移植患者的实验性细胞疗法 Orca-T&#xff0c;获得了美国…

C++求复数的角度_万物皆可傅里叶?复数傅里叶变换详解

来源&#xff1a;新浪博客&#xff0c;仅作学术交流&#xff0c;如有侵权请联系删文。 说的广义一点&#xff0c;"复数"是一个"概念"&#xff0c;不是一种客观存在。 什么是"概念"? 一张纸有几个面? 两个&#xff0c;这里"面"是一…

函数式接口Stream类

一、Stream概述 1.1 关于流的简介 Java8是一个非常成功的版本&#xff0c;新增的Stream&#xff0c;配合同版本出现的Lambda&#xff0c;为我们操作集合提供了极大的便利。 ​ Stream 是 Java8 中处理集合的关键抽象概念&#xff0c;它可以指定我们希望对集合进行的操作&…

基本极限定理(切比雪夫不等式,大数定律,中心极限定理)

人们在长期的实践中发现,虽然个别事件在某次试验中可能发生也可能不发生,但在大量重复实验中却呈现明显的规律性,即一个随机事件发生的频率在某个固定数的附近摇摆,这就是所谓“频率的稳定性”。 这里介绍的就是概率论的理论基础!戳这里:概率论思维导图 切比雪夫不等式…

机器人 沈为民_科技智能重构创作力 创意产业弯道超车

原标题&#xff1a;科技智能重构创作力 创意产业弯道超车 【记者邱登科】 一场题为“科技智能如何重构创作力”的学术研讨会日前在广州美术学院举行。记者在研讨会了解到&#xff0c;目前人工智能、生物技术、虚拟现实技术、纳米技术、4D智能打印、量子科技等高科技在快速发展。…

大话信号与系统 --- 奇文共欣赏

大话信号与系统 前言&#xff1a;大家都知道《信号与系统》是一门很难的课&#xff0c;很多人虽然学过了&#xff0c;但其实什么也没得到&#xff0c;今天给大家推荐这篇文章&#xff0c;看了之后&#xff0c;相信你会有收获。 第一课 什么是卷积&#xff1f;卷积有什么用&…

我彻底服了,大牛讲解信号与系统(通俗易懂)

我彻底服了,大牛讲解信号与系统(通俗易懂) (2015-10-13 21:22:36) 转载▼ 分类&#xff1a; 电力电子技术 第一课什么是卷积卷积有什么用什么是傅利叶变换什么是拉普拉斯变换 引子 很多朋友和我一样&#xff0c;工科电子类专业&#xff0c;学了一堆信号方面的课&#xff0c;…

8分钟带你彻底弄懂《信号与系统》

本文转载来自&#xff1a;《信号与系统》太easy了 那是因为看过了这篇奇文 大家都知道《信号与系统》是一门很难的课&#xff0c;很多人虽然学过了&#xff0c;但其实什么也没得到&#xff0c;今天给大家推荐这篇文章&#xff0c;看了之后&#xff0c;相信你会有收获。 第一课 …

奥特曼系列服务器芝庞顿,芝庞顿解析

该楼层疑似违规已被系统折叠 隐藏此楼查看此楼 普攻上等,物理直线高概率三连,尤其是+16之后必定二连,结合12被动目标同时带毒和烧时最终伤害+160W,三连下来有着480W无视防御的终伤(普攻开始时计算诱拐命中和终伤加成,之后的追击不会再触发诱拐和终伤加成,加成持续到芝庞顿…

让我们来认识一下信号与系统的关系

第一课什么是卷积卷积有什么用什么是傅利叶变换什么是拉普拉斯变换 引子 很多朋友和我一样&#xff0c;工科电子类专业&#xff0c;学了一堆信号方面的课&#xff0c;什么都没学懂&#xff0c;背了公式考了试&#xff0c;然后毕业了。 先说"卷积有什么用"这个问题。…

大牛讲解信号与系统以及数字信号处理

注&#xff1a;找不到原始出处&#xff0c;sorry. 第一课 什么是卷积 卷积有什么用 什么是傅利叶变换 什么是拉普拉斯变换 引子 很多朋友和我一样&#xff0c;工科电子类专业&#xff0c;学了一堆信号方面的课&#xff0c;什么都没学懂&#xff0c;背了公式考了试&#xff0c;然…

当在线纠纷解决遇到区块链:去中心化司法的诞生

在线纠纷解决&#xff08;ODR&#xff09;诞生于20世纪90年代。随着互联网成为人们日常生活的一部分&#xff0c;许多人试图利用互联网建立虚拟法庭&#xff0c;以大幅度提高纠纷解决程序的效率。然而&#xff0c;这一愿望至今未能完全实现。在某种程度上&#xff0c;早期的ODR…

Java-面向对象进阶

目录 一、static静态关键字 1.static是什么、修饰成员变量的用法 2.static修饰成员变量的内存原理 3.static修饰成员方法的基本用法 4.static修饰成员方法的内存原理 5.static的注意事项 二、static应用知识&#xff1a;工具类 1.工具类概述 2.练习-定义数组工具类 三…

《物理世界》公布2022年度十大突破

来源&#xff1a;科技日报 近日&#xff0c;英国《物理世界》杂志公布了2022年度十大突破&#xff0c;涵盖从量子、医学物理学、天文学到凝聚态物质等各个方面。这十项突破是由《物理世界》编辑小组从今年在该杂志网站上发布的涵盖物理学所有领域的数百项研究中精选出来的。 开…

服务器宠物系统,4月27日服务器公告:宠物训练师等级系统开启

2012年4月25日 相信小洛克已经听说了很多关于王国守护者的传闻吧&#xff01;他究竟是一个怎样的荣誉让小洛克们争先恐后的追求呢&#xff1f;在本次的更新中&#xff0c;期待已久的宠物训练师等级系统开启了&#xff0c;为了荣誉&#xff0c;战斗吧&#xff01;少年&#xff0…

PT_中心极限定理CLT:棣莫佛-拉普拉斯定理de Moivre - Laplace CLT+林德伯格-列维(Lindeberg-Levy)定理

中心极限定理CLT 中心极限定理&#xff08;英语&#xff1a;central limit theorem&#xff0c;简作 CLT&#xff09;是概率论中的一组定理。 中心极限定理说明&#xff0c;在适当的条件下&#xff0c;大量相互独立随机变量的均值经适当标准化后依分布收敛于标准正态分布。这组…