【题解 动态规划】 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 一、介绍 命令模式使得请求的发送者与请求的执行者之间消除耦合,让对象之间的调用关系更加灵活。在命令模…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...
