I bumped into a girl literally_back and forth

I bumped into a girl literally_back and forthhttp://acm.hznu.edu.cn/OJ/problem.php?cid=1263&pid=6http://acm.hznu.edu.cn/OJ/problem.php?id=2585题意:每天能往存钱罐加任意实数的钱,每天不能多于起那一天放的钱数。如果某一天的钱数恰好等于那天的特价商品,则可以买,求最后的最大快乐值。题解:显然的贪心:如果第i天买完,准备在第…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

http://acm.hznu.edu.cn/OJ/problem.php?cid=1263&pid=6

http://acm.hznu.edu.cn/OJ/problem.php?id=2585

题意:每天能往存钱罐加任意实数的钱,每天不能多于起那一天放的钱数。如果某一天的钱数恰好等于那天的特价商品,则可以买,求最后的最大快乐值。

题解:

  显然的贪心:如果第i天买完,准备在第j天买,那么显然最优是在i+1j天放wi/(j-i)的钱。

  于是假定选择的物品是k1,k2,k3

  那么必须满足a[ki]/(ki-ki-1)<=a[ki-1]/(ki-1-ki-2)

  f[i][j]表示最后购买的两个物品为ij,则f[i][j]=max(f[j][k]+v[i]) (j->k->i合法)

  观察到上述条件可以把k分离,即k>=j-(i-j)*a[j]/a[i],因此可以维护前缀和来使得时间复杂度变为O(n2)

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/203608.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 动态规划优缺点_巴西优化航空路线利用率

    动态规划优缺点_巴西优化航空路线利用率C 国有 n 个大城市和 m 条道路,每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的道路在统计条数时也计为 1 条。C 国幅员辽阔,各地的资源分布情况各不相同,这就导致了同一种商品在不同城市的价格不一定相同。但是,同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来到 C 国旅游。当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后,便决定在旅游的同时,利用商品在

  • docker(5)docker运行web应用

    docker(5)docker运行web应用前言前面我们运行的容器并没有一些什么特别的用处。接下来让我们尝试使用docker构建一个web应用程序。我们将在docker容器中运行一个PythonFlask应用来运行一个web

  • org.apache.http.ProtocolException: Target host is not specified

    org.apache.http.ProtocolException: Target host is not specified

  • drupal教程 Drupal的电子商务模块(ecommerce module)[通俗易懂]

    drupal教程 Drupal的电子商务模块(ecommerce module)[通俗易懂]译者:老葛Drupal自身并没有自带一个电子商务模块,但是开发者贡献了一个电子商务模块E-commercemodule。事实上,还有一个模块ubercartmodule,后者看起来功能更强大一些,而且后者有专门的论坛和开发者。但是我还是选择了前者,这个更简单一些的ecommercemodule。原因很简单,与电子商务相关的是支付功能,对于前者来说,存在着大量的各个支付网管的模块功

  • 从ZERO开始系列:大数据软件之1.Hadoop的安装与wordcount运行

    从ZERO开始系列:大数据软件之1.Hadoop的安装与wordcount运行

  • Linux VI文本编辑器

    Linux VI文本编辑器VI文本编辑器  学会使用vi编辑器是学习Linux系统的必备技术之一,因为一般的Linux服务器是没有GUI界面的,Linux运维及开发人员基本上都是通过命令行的方式进行文本编辑或程序编写的。vi编辑器是Linux内置的文本编辑器,几乎所有的类unix系统中都内置了vi编辑器,而其它编辑器则不一定,另外很多软件会调用vi编辑进行内容编写,例如cront…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号