当前位置: 首页 > news >正文

???ABC366:F - Maximum Composition(dp,无序:贪心排序)

问题陈述

给你 NN 个线性函数 f1,f2,…,fNf1​,f2​,…,fN​ ,其中 fi(x)=Aix+Bifi​(x)=Ai​x+Bi​ .

求由 KK 组成的序列 p=(p1,p2,…,pK)p=(p1​,p2​,…,pK​) 中 fp1(fp2(…fpK(1)…))fp1​​(fp2​​(…fpK​​(1)…)) 的最大可能值。介于 11 和 NN (含)之间的个不同整数的最大可能值 fp1(fp2(…fpK(1)…))fp1​​(fp2​​(…fpK​​(1)…)) 。

限制因素
  • 1≤N≤2×1051≤N≤2×105
  • 1≤K≤min(N,10)1≤K≤min(N,10)
  • 1≤Ai,Bi≤501≤Ai​,Bi​≤50 (1≤i≤N)(1≤i≤N)
  • 所有输入值均为整数。
做法

我们看到这题肯定是想到了dp。但是吧,这题是要考虑顺序的,就是从n个中选k个,这k个数字的顺序会影响答案。那怎么办呢,我们肯定是不想要去考虑那个顺序的,我们就想把它先排好序。那就看看他能不能排序。我们假设i排在j前更好,那么就有Ai(Aj+Bj) + Bi > Aj(Ai+Bi) + Bj,即Ai*Bj + Bi > Aj*Bi + Bj。把i和i的放在一起,且i的必须放在左边,不然会出错,可能是我们已经加设了i排在j前更好吧,不太懂。然后得到Bi-AjBi > Bj-AiBj,即Bi(1-Aj) > Bj(1-Ai)。然后你可以选择用Bi(1-Aj)排序,或者Bj(1-Ai)排序。

排完序就好办了,dp数组下标:第i到n个选了j个 ; 值:f函数的总值。我们为啥要倒着从n到1来遍历呢,因为函数是从外到里嵌套的,就是根据那个排序来的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
int dp[200010][20];//下标:第i到n个选了j个  值:f函数的总值 bool cmp(pair<int,int> a,pair<int,int> b){//贪心 //return b.second*(a.first-1) > b.first*(a.second-1);错误的return 1ll*a.second*(1-b.first)>1ll*b.second*(1-a.first);
}signed main(){scanf("%lld%lld",&n,&k);vector< pair<int,int> > v(n+1);for(int i=1;i<=n;i++){cin>>v[i].first>>v[i].second;}sort(v.begin()+1,v.end(),cmp);for(int i=1;i<=n+1;i++){for(int j=0;j<=10;j++){dp[i][j]=-1e6;}}dp[n+1][0]=1;//起初f(x)函数的x是1 for(int i=n;i>=1;i--){for(int j=0;j<=k;j++){dp[i][j]=max(dp[i][j],dp[i+1][j]);//不选 if(j) dp[i][j]=max(dp[i][j],1ll*v[i].first*dp[i+1][j-1]+v[i].second);}}cout<<dp[1][k];}
最后

还是不太理解吧,那个排序函数写的,我改成别的都过不去。

相关文章:

???ABC366:F - Maximum Composition(dp,无序:贪心排序)

问题陈述 给你 NN 个线性函数 f1,f2,…,fNf1​,f2​,…,fN​ &#xff0c;其中 fi(x)AixBifi​(x)Ai​xBi​ . 求由 KK 组成的序列 p(p1,p2,…,pK)p(p1​,p2​,…,pK​) 中 fp1(fp2(…fpK(1)…))fp1​​(fp2​​(…fpK​​(1)…)) 的最大可能值。介于 11 和 NN (含)之间的个不…...

unity项目打包为webgl后应用于vue项目中(iframe模式)的数据交互

参考文章&#xff1a; 1.Unity打包WebGL: 导入Vue 2.unity文档-WebGL&#xff1a;与浏览器脚本交互 3.unity与vue交互(无第三方插件&#xff09; 目录 一、前期工作1.新建.jslib文件2.新建.cs脚本3. 新建一个Text对象和button按钮对象4.添加脚本空对象UIEvent5.导出unity为w…...

【数据结构与算法 | 图篇】Bellman-Ford算法(单源最短路径算法)

1. 前言 前文的迪杰斯特拉算法不能求解有负边的图的最短路径的问题。而此文的Bellman-Ford可以处理含负权边的图算法&#xff0c;并且能检测出图中是否存在负环&#xff08;权重和为负数的环&#xff09;. 2. 基本思想 1. 初始化&#xff1a; 对于所有顶点 v ∈ V \ {s}&am…...

Python | Leetcode Python题解之第336题回文对

题目&#xff1a; 题解&#xff1a; class Solution:def palindromePairs1(self, words: List[str]) -> List[List[int]]:# 核心思想--枚举前缀和后缀# 如果两个字符串k1&#xff0c;k2组成一个回文字符串会出现三种情况# len(k1) len(k2),则需要比较k1 k2[::-1]# len(k1…...

C语言家教记录(六)

导语 本次授课的内容如下&#xff1a;指针&#xff0c;指针和数组 辅助教材为 《C语言程序设计现代方法&#xff08;第2版&#xff09;》 指针 指针变量 计算机按字节划分地址&#xff0c;每个地址访问一个字节 指针变量指向变量的地址&#xff0c;指的是变量第一个字节的…...

C++竞赛初阶L1-11-第五单元-for循环(25~26课)519: T454430 人口增长问题

题目内容 假设目前的世界人口有 x 亿&#xff0c;按照每年 0.1% 的增长速度&#xff0c;n 年后将有多少人&#xff1f; 输入格式 一行两个正整数 x 和 n&#xff0c;之间有一个空格。其中&#xff0c;1≤x≤100,1≤n≤100。 输出格式 一行一个数&#xff0c;表示答案。以亿…...

demo测试

目录 接口commonCodeGenerator entityuser mapperUserMapper controllerUserController serviceUserServiceimplUserServiceImpl mapper.xmlpom.xmlapplication.yml 接口 common CodeGenerator package com.llz.demo.common;import com.baomidou.mybatisplus.core.exceptions…...

TinTinLand Web3 + DePIN 共学月|深入探索 DePIN 项目,全景分析去中心化网络未来

「TinTinLand Web3 主题共学月」是由 TinTinLand 每月发起的主题学习活动&#xff0c;携手知名项目共同打造一个系统化、互动性强的学习平台&#xff0c;帮助开发者不断提升技能&#xff0c;紧跟 Web3 技术的前沿发展。活动通过演示视频、学习打卡、模拟环境、实际操作等多种方…...

Java并发编程(六)

1、java 中有几种方法可以实现一个线程 继承 Thread 类实现 Runnable 接口实现 Callable 接口&#xff0c;需要实现的是 call() 方法 2、如何停止一个正在运行的线程 使用共享变量的方式 在这种方式中&#xff0c;之所以引入共享变量&#xff0c;是因为该变量可以被多个执行…...

k8s对外服务之Ingress

目录 1.Ingress 简介 2.Ingress 组成 3.Ingress-Nginx 工作原理 4.部署 nginx-ingress-controller 5.总结 1.Ingress 简介 service的作用体现在两个方面&#xff0c;对集群内部&#xff0c;它不断跟踪pod的变化&#xff0c;更新endpoint中对应pod的对象&#xff0c;提供了…...

使用Python+moviepy在视频画面上绘制边框

一、 使用VideoFileClip对象的的fx函数设置vfx.margin&#xff0c;在视频画面上绘制边框 from moviepy.editor import * mvVideoFileClip(/home/Download/leaves.mp4) mv2mv.fx(vfx.margin,mar3,color(0,0,255),opacity0.5) # 绘制边框# mar3 &#xff1a;边框宽度3像素&#…...

灵办AI探索之旅:颠覆传统的代码开发工具

前言 灵办AI是一个先进的人工智能工具&#xff0c;专注于提高软件开发和项目管理的效率。其核心功能包括代码生成、优化、评估和自动化修复&#xff0c;旨在帮助开发者和团队提升开发速度和代码质量。 体验地址&#xff1a;https://ilingban.com/browser_extension/?fromjj …...

【Redis】Redis 数据类型与结构—(二)

Redis 数据类型与结构 一、值的数据类型二、键值对数据结构三、集合数据操作效率 一、值的数据类型 Redis “快”取决于两方面&#xff0c;一方面&#xff0c;它是内存数据库&#xff0c;另一方面&#xff0c;则是高效的数据结构。 Redis 键值对中值的数据类型&#xff0c;也…...

Tomcat初篇

目录 Tomcat主要特点Tomcat的核心组件Tomcat使用安装Tomcat配置Tomcat启动和停止Tomcat Tomcat工作原理目录结构配置文件性能优化策略 Tomcat Apache Tomcat是一个开源的Servlet容器和Web服务器&#xff0c;广泛用于运行基于Java的Web应用程序。它实现了Java Servlet和JavaSer…...

机器学习(2)-- KNN算法之手写数字识别

KNN算法 KNN&#xff08;K-Nearest Neighbor&#xff0c;K最近邻&#xff09;算法是一种用于分类和回归的非参数统计方法&#xff0c;尤其在分类问题中表现出色。在手写数字识别领域&#xff0c;KNN算法通过比较测试样本与训练样本之间的距离&#xff0c;找到最近的K个邻居&am…...

【机器人】关于钉钉机器人如何进行自定义开发问答【详细清晰】

目标&#xff1a;当用户输入问题并钉钉机器人&#xff0c;钉钉机器人进行相应的回答&#xff0c;达到一种交互问答的效果 开发文档参考&#xff1a;https://open.dingtalk.com/document/orgapp/robot-overview 首先进行登录企业&#xff0c;后面如果没有进行登录&#xff0c;会…...

Qt:exit,quit,close的用法及区别

前言 虽然能从单词的字面意思大致理解这些函数的意思&#xff0c;但是总感觉不出来它们的区别以及用法&#xff0c;特地去研究一下 正文 在 Qt 中&#xff0c;quit、exit 和 close 都是用于终止程序或关闭窗口的方法 1. QApplication::quit() 注意&#xff1a;注意quit() …...

Linux——进程地址空间

前言 在操作系统中&#xff0c;内存分为以下几个区域&#xff0c;从下往上按照从小到大排列 一、程序地址的分布 代码 #include <stdio.h> #include <stdlib.h> int noval; int val 1;int main(int argc,char*argv[],char*env[]){printf("code addr %p\n&q…...

信创(国产化)方案

信创 信创,即信息技术应用创新,旨在实现信息技术自主可控openEuler openEuler是一款开源、免费的操作系统,由openEuler社区运作,前身为运行在华为公司通用服务器上的操作系统EulerOS。openEuler作为一款开源、免费的操作系统,由开放原子开源基金会(OpenAtom Foundation)…...

EasyRecovery17中文版永久汉化版电脑数据恢复工具下载

&#x1f388;&#x1f389;安利时间到&#xff01;今天要跟大家分享的是——EasyRecovery17中文版的最新功能&#xff01;&#x1f389;&#x1f388; &#x1f31f;✨ “数据恢复小能手” ✨&#x1f31f; 让我来介绍一下这款软件的主打特点。 EasyRecovery17中文版是一款强…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

rknn toolkit2搭建和推理

安装Miniconda Miniconda - Anaconda Miniconda 选择一个 新的 版本 &#xff0c;不用和RKNN的python版本保持一致 使用 ./xxx.sh进行安装 下面配置一下载源 # 清华大学源&#xff08;最常用&#xff09; conda config --add channels https://mirrors.tuna.tsinghua.edu.cn…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...

JavaScript 标签加载

目录 JavaScript 标签加载script 标签的 async 和 defer 属性&#xff0c;分别代表什么&#xff0c;有什么区别1. 普通 script 标签2. async 属性3. defer 属性4. type"module"5. 各种加载方式的对比6. 使用建议 JavaScript 标签加载 script 标签的 async 和 defer …...