【题解 动态规划】 Colored Rectangles
题目描述:

分析:
乍一看我还以为是贪心!
猫 想想感觉没问题
但是局部最优并不能保证全局最优
比如这组数据
19 19 19 19
20 20
20 20
如果按照贪心的做法,答案是20*20*2
但是其实答案是19*20*4
因此这道题用贪心是不对的
于是我们考虑dp
可以观察到这道题的n非常小只有200
这就暗示我们这道题可以用 n 3 n^3 n3的做法去解决
那么我们就可以这样设dp状态
f [ i ] [ j ] [ k ] 表示用三个颜色分别用了前 i , j , k 个数,所能获得的最大价值 f[i][j][k]表示用三个颜色分别用了前i,j,k个数,所能获得的最大价值 f[i][j][k]表示用三个颜色分别用了前i,j,k个数,所能获得的最大价值
如何转移呢?
考虑一次可以取两个数
也就是说可以取12,23,13
那么分别从这三种状态转移过来即可
有的时候记忆化搜索比dp更好写!
Code
#include<bits/stdc++.h>
using namespace std;const int N = 210;
int r,g,bb;
int a[N],b[N],c[N];
int f[N][N][N];bool cmp(int x,int y){return x>y;
}int Dfs(int x,int y,int z){if (f[x][y][z]) return f[x][y][z];int Max = 0;if (x && y) Max = max(Max,Dfs(x-1,y-1,z)+a[x]*b[y]);if (x && z) Max = max(Max,Dfs(x-1,y,z-1)+a[x]*c[z]);if (z && y) Max = max(Max,Dfs(x,y-1,z-1)+b[y]*c[z]);return f[x][y][z] = Max;
}int main(){cin>>r>>g>>bb;for (int i = 1; i <= r; i++) cin>>a[i];for (int i = 1; i <= g; i++) cin>>b[i];for (int i = 1; i <= bb; i++) cin>>c[i];sort(a+1,a+r+1);sort(b+1,b+g+1);sort(c+1,c+bb+1);cout<<Dfs(r,g,bb)<<endl;return 0;
}
相关文章:
【题解 动态规划】 Colored Rectangles
题目描述: 分析: 乍一看我还以为是贪心! 猫 想想感觉没问题 但是局部最优并不能保证全局最优 比如这组数据 19 19 19 19 20 20 20 20如果按照贪心的做法,答案是20*20*2 但是其实答案是19*20*4 因此这道题用贪心是不对的 于是我…...
VsCode好用的扩展插件
开发插件推荐: 别名路径跳转 >> 点击引用的变量名,ctrl 点击 跳转文件Auto Rename Tag >> 修改标签前缀,后缀标签会同时修改Chinees 中文(简体)Code Runner >> 纯js文件右键点击run code即可底部终端打印file-icons-mac >> ma…...
Linux shell编程学习笔记4:修改命令行提示符格式(内容和颜色)
一、命令行提示符格式内容因shell类型而异 Linux终端命令行提示符内容格式则因shell的类型而异,例如CoreLinux默认的shell是sh,其命令行提示符为黑底白字,内容为: tcbox:/$ 其中,tc为当前用户名,box为主机…...
vue-引入使用main.js全局常量
common.js 命名什么都可以,用来定义常量的 定义了之后使用export让此暴露出去 const QRaddress http://localhost:9875export{QRaddress, } main.js //引入刚刚的js import {QRaddress} from /config/common.js挂载 Vue.prototype.$QRaddress QRaddress使用 …...
【C语言】【动态内存管理】malloc,free,calloc,realloc
1.malloc函数 void* malloc(size_t size)功能:向内存申请字节为 size大小的空间 使用时要包含头文件:<stdlib.h> 开辟成功:返回开辟好的空间初始地址的指针 开辟失败:返回空指针 NULL 使用举例: (malloc和free…...
Linux性能优化--性能工具-系统CPU
2.0.概述 本章概述了系统级的Linux性能工具。这些工具是你追踪性能问题时的第一道防线。它们能展示整个系统的性能情况和哪些部分表现不好。 1.理解系统级性能的基本指标,包括CPU的使用情况。 2.明白哪些工具可以检索这些系统级性能指标。 2.1CPU性能统计信息 为…...
Ipython和Jupyter Notebook介绍
Ipython和Jupyter Notebook介绍 Python、IPython和Jupyter Notebook是三个不同但密切相关的工具。简而言之,Python是编程语言本身,IPython是对Python的增强版本,而Jupyter Notebook是一种在Web上进行交互式计算的环境,使用IPytho…...
数列极差(c++题解)
题目描述 佳佳的老师在黑板上写了一个由 n个正整数组成的数列,要求佳佳进行如下操作:每次擦去其中的两个数a 和b ,然后在数列中加入一个数a*b1 ,如此下去直至黑板上剩下一个数为止,在所有按这种操作方式最后得到的数…...
面试题:熟悉设计模式吗?谈谈简单工厂模式和策略模式的区别
刚刚接触设计模式的时候,我相信单例模式和工厂模式应该是用的最多的,毕竟很多的底层代码几乎都用了这些模式。自从接触了一次阿里的公众号发的一次文章关于 DDD的使用 以后,就逐渐接触了策略模式。现在在项目中运用最多的也是这几种设计模式了…...
Windows + Git + TortoiseGit + Github
一、下载Git(Git For Windows) 1.1. Git下载地址:https://gitforwindows.org/ 1.2. 默认安装即可(包名:Git-2.42.0.2-64-bit.exe) 二、下载TortoiseGit 2.1.TortoiseGit下载地址:http://tortoi…...
MySQL数据库索引练习
1.学生表:Student (Sno, Sname, Ssex , Sage, Sdept) 学号,姓名,性别,年龄,所在系 Sno为主键 课程表:Course (Cno, Cname,) 课程号,课程名 Cno为主键 学生选课表:SC (Sno, Cno, Scor…...
mysql面试题10:MySQL中有哪几种锁?表级锁、行级锁、页面锁区别和联系?
该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:Mysql中有哪几种锁? 在MySQL中,主要有以下几种类型的锁: 共享锁(Shared Lock):也称为读锁。多个事务可以同时持有共享锁,可以读取但不能修…...
ctfshow—1024系列练习
1024 柏拉图 有点像rce远程执行,有四个按钮,分别对应四份php文件,开始搞一下。一开始,先要试探出 文件上传到哪里? 怎么读取上传的文件? 第一步:试探上传文件位置 直接用burp抓包,…...
javaWeb学生信息管理
一、引言 学生信息管理系统是基于Java Web技术开发的一个全栈应用,用于管理学生的基本信息。本系统采用Eclipse作为开发工具,Navicat用于MySQL数据库管理,运行在JDK1.8、Tomcat9.0、MySQL8.0环境下。前端采用JavaScript、jQuery、Bootstrap4…...
玩转gpgpu-sim 04记—— __cudaRegisterBinary() of gpgpu-sim 到底做了什么
官方文档: GPGPU-Sim 3.x Manual __cudaRegisterBinary(void*) 被执行到的代码逻辑如下: void** CUDARTAPI __cudaRegisterFatBinary( void *fatCubin ) { #if (CUDART_VERSION < 2010)printf("GPGPU-Sim PTX: ERROR ** this version of GPGPU…...
S-Clustr(影子集群)僵尸网络@Мартин.
公告 项目地址:https://github.com/MartinxMax/S-Clustr/tree/V1.0.0 1.成功扩展3类嵌入式设备,组建庞大的"僵尸网络" |——C51[开发中] |——Arduino |——合宙AIR780e[开发中] 2.攻击者端与服务端之间通讯过程全程加密,防溯源分析 3.Generate一键自动生成Arduino…...
认识PostgreSQL
深入认识PostgreSQL:开源世界的强大数据库 在当今数字化时代,数据是组织的最宝贵资源之一。数据库管理系统(DBMS)扮演着关键角色,帮助企业存储、管理和分析数据。PostgreSQL,作为一款开源的高级关系型数据库…...
基本的五大排序算法
目录: 一,直接插入算法 二,希尔排序算法 三,选择排序 四,堆排序 五,冒泡排序算法 简介: 排序算法目前是我们最常用的算法之一,据研究表明,目前排序占用计算机CPU的时…...
封装api的理解
1.基地址(baseUrl) (1).测试环境 用于测试环境的运行 (2).正式环境 用于正式环境的运行 2.拦截器 1.请求拦截器 (1)成功的回调 做的事情:例如在请求头header里面加入toekn。 (2)失败的回调 直接返回失败的结果: return promise.reject(error) 2.响应拦截器 (1)成功的回…...
Unity实现设计模式——命令模式
Unity实现设计模式——命令模式 推荐一个Unity学习设计模式很好的GitHub地址:https://github.com/QianMo/Unity-Design-Pattern 有非常多的Star 一、介绍 命令模式使得请求的发送者与请求的执行者之间消除耦合,让对象之间的调用关系更加灵活。在命令模…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
