???ABC366:F - Maximum Composition(dp,无序:贪心排序)
问题陈述
给你 NN 个线性函数 f1,f2,…,fNf1,f2,…,fN ,其中 fi(x)=Aix+Bifi(x)=Aix+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 ,其中 fi(x)AixBifi(x)AixBi . 求由 KK 组成的序列 p(p1,p2,…,pK)p(p1,p2,…,pK) 中 fp1(fp2(…fpK(1)…))fp1(fp2(…fpK(1)…)) 的最大可能值。介于 11 和 NN (含)之间的个不…...
unity项目打包为webgl后应用于vue项目中(iframe模式)的数据交互
参考文章: 1.Unity打包WebGL: 导入Vue 2.unity文档-WebGL:与浏览器脚本交互 3.unity与vue交互(无第三方插件) 目录 一、前期工作1.新建.jslib文件2.新建.cs脚本3. 新建一个Text对象和button按钮对象4.添加脚本空对象UIEvent5.导出unity为w…...
【数据结构与算法 | 图篇】Bellman-Ford算法(单源最短路径算法)
1. 前言 前文的迪杰斯特拉算法不能求解有负边的图的最短路径的问题。而此文的Bellman-Ford可以处理含负权边的图算法,并且能检测出图中是否存在负环(权重和为负数的环). 2. 基本思想 1. 初始化: 对于所有顶点 v ∈ V \ {s}&am…...
Python | Leetcode Python题解之第336题回文对
题目: 题解: class Solution:def palindromePairs1(self, words: List[str]) -> List[List[int]]:# 核心思想--枚举前缀和后缀# 如果两个字符串k1,k2组成一个回文字符串会出现三种情况# len(k1) len(k2),则需要比较k1 k2[::-1]# len(k1…...
C语言家教记录(六)
导语 本次授课的内容如下:指针,指针和数组 辅助教材为 《C语言程序设计现代方法(第2版)》 指针 指针变量 计算机按字节划分地址,每个地址访问一个字节 指针变量指向变量的地址,指的是变量第一个字节的…...
C++竞赛初阶L1-11-第五单元-for循环(25~26课)519: T454430 人口增长问题
题目内容 假设目前的世界人口有 x 亿,按照每年 0.1% 的增长速度,n 年后将有多少人? 输入格式 一行两个正整数 x 和 n,之间有一个空格。其中,1≤x≤100,1≤n≤100。 输出格式 一行一个数,表示答案。以亿…...
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 每月发起的主题学习活动,携手知名项目共同打造一个系统化、互动性强的学习平台,帮助开发者不断提升技能,紧跟 Web3 技术的前沿发展。活动通过演示视频、学习打卡、模拟环境、实际操作等多种方…...
Java并发编程(六)
1、java 中有几种方法可以实现一个线程 继承 Thread 类实现 Runnable 接口实现 Callable 接口,需要实现的是 call() 方法 2、如何停止一个正在运行的线程 使用共享变量的方式 在这种方式中,之所以引入共享变量,是因为该变量可以被多个执行…...
k8s对外服务之Ingress
目录 1.Ingress 简介 2.Ingress 组成 3.Ingress-Nginx 工作原理 4.部署 nginx-ingress-controller 5.总结 1.Ingress 简介 service的作用体现在两个方面,对集群内部,它不断跟踪pod的变化,更新endpoint中对应pod的对象,提供了…...
使用Python+moviepy在视频画面上绘制边框
一、 使用VideoFileClip对象的的fx函数设置vfx.margin,在视频画面上绘制边框 from moviepy.editor import * mvVideoFileClip(/home/Download/leaves.mp4) mv2mv.fx(vfx.margin,mar3,color(0,0,255),opacity0.5) # 绘制边框# mar3 :边框宽度3像素&#…...
灵办AI探索之旅:颠覆传统的代码开发工具
前言 灵办AI是一个先进的人工智能工具,专注于提高软件开发和项目管理的效率。其核心功能包括代码生成、优化、评估和自动化修复,旨在帮助开发者和团队提升开发速度和代码质量。 体验地址:https://ilingban.com/browser_extension/?fromjj …...
【Redis】Redis 数据类型与结构—(二)
Redis 数据类型与结构 一、值的数据类型二、键值对数据结构三、集合数据操作效率 一、值的数据类型 Redis “快”取决于两方面,一方面,它是内存数据库,另一方面,则是高效的数据结构。 Redis 键值对中值的数据类型,也…...
Tomcat初篇
目录 Tomcat主要特点Tomcat的核心组件Tomcat使用安装Tomcat配置Tomcat启动和停止Tomcat Tomcat工作原理目录结构配置文件性能优化策略 Tomcat Apache Tomcat是一个开源的Servlet容器和Web服务器,广泛用于运行基于Java的Web应用程序。它实现了Java Servlet和JavaSer…...
机器学习(2)-- KNN算法之手写数字识别
KNN算法 KNN(K-Nearest Neighbor,K最近邻)算法是一种用于分类和回归的非参数统计方法,尤其在分类问题中表现出色。在手写数字识别领域,KNN算法通过比较测试样本与训练样本之间的距离,找到最近的K个邻居&am…...
【机器人】关于钉钉机器人如何进行自定义开发问答【详细清晰】
目标:当用户输入问题并钉钉机器人,钉钉机器人进行相应的回答,达到一种交互问答的效果 开发文档参考:https://open.dingtalk.com/document/orgapp/robot-overview 首先进行登录企业,后面如果没有进行登录,会…...
Qt:exit,quit,close的用法及区别
前言 虽然能从单词的字面意思大致理解这些函数的意思,但是总感觉不出来它们的区别以及用法,特地去研究一下 正文 在 Qt 中,quit、exit 和 close 都是用于终止程序或关闭窗口的方法 1. QApplication::quit() 注意:注意quit() …...
Linux——进程地址空间
前言 在操作系统中,内存分为以下几个区域,从下往上按照从小到大排列 一、程序地址的分布 代码 #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中文版永久汉化版电脑数据恢复工具下载
🎈🎉安利时间到!今天要跟大家分享的是——EasyRecovery17中文版的最新功能!🎉🎈 🌟✨ “数据恢复小能手” ✨🌟 让我来介绍一下这款软件的主打特点。 EasyRecovery17中文版是一款强…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...
CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!
本文介绍了一种名为AnomalyAny的创新框架,该方法利用Stable Diffusion的强大生成能力,仅需单个正常样本和文本描述,即可生成逼真且多样化的异常样本,有效解决了视觉异常检测中异常样本稀缺的难题,为工业质检、医疗影像…...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
