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

【题解 动态规划】 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

题目描述&#xff1a; 分析&#xff1a; 乍一看我还以为是贪心&#xff01; 猫 想想感觉没问题 但是局部最优并不能保证全局最优 比如这组数据 19 19 19 19 20 20 20 20如果按照贪心的做法&#xff0c;答案是20*20*2 但是其实答案是19*20*4 因此这道题用贪心是不对的 于是我…...

VsCode好用的扩展插件

开发插件推荐: 别名路径跳转 >> 点击引用的变量名&#xff0c;ctrl 点击 跳转文件Auto Rename Tag >> 修改标签前缀&#xff0c;后缀标签会同时修改Chinees 中文(简体)Code Runner >> 纯js文件右键点击run code即可底部终端打印file-icons-mac >> ma…...

Linux shell编程学习笔记4:修改命令行提示符格式(内容和颜色)

一、命令行提示符格式内容因shell类型而异 Linux终端命令行提示符内容格式则因shell的类型而异&#xff0c;例如CoreLinux默认的shell是sh&#xff0c;其命令行提示符为黑底白字&#xff0c;内容为&#xff1a; tcbox:/$ 其中&#xff0c;tc为当前用户名&#xff0c;box为主机…...

vue-引入使用main.js全局常量

common.js 命名什么都可以&#xff0c;用来定义常量的 定义了之后使用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)功能&#xff1a;向内存申请字节为 size大小的空间 使用时要包含头文件&#xff1a;<stdlib.h> 开辟成功&#xff1a;返回开辟好的空间初始地址的指针 开辟失败&#xff1a;返回空指针 NULL 使用举例&#xff1a; (malloc和free…...

Linux性能优化--性能工具-系统CPU

2.0.概述 本章概述了系统级的Linux性能工具。这些工具是你追踪性能问题时的第一道防线。它们能展示整个系统的性能情况和哪些部分表现不好。 1.理解系统级性能的基本指标&#xff0c;包括CPU的使用情况。 2.明白哪些工具可以检索这些系统级性能指标。 2.1CPU性能统计信息 为…...

Ipython和Jupyter Notebook介绍

Ipython和Jupyter Notebook介绍 Python、IPython和Jupyter Notebook是三个不同但密切相关的工具。简而言之&#xff0c;Python是编程语言本身&#xff0c;IPython是对Python的增强版本&#xff0c;而Jupyter Notebook是一种在Web上进行交互式计算的环境&#xff0c;使用IPytho…...

数列极差(c++题解)

题目描述 佳佳的老师在黑板上写了一个由 n个正整数组成的数列&#xff0c;要求佳佳进行如下操作&#xff1a;每次擦去其中的两个数a 和b &#xff0c;然后在数列中加入一个数a*b1 &#xff0c;如此下去直至黑板上剩下一个数为止&#xff0c;在所有按这种操作方式最后得到的数…...

面试题:熟悉设计模式吗?谈谈简单工厂模式和策略模式的区别

刚刚接触设计模式的时候&#xff0c;我相信单例模式和工厂模式应该是用的最多的&#xff0c;毕竟很多的底层代码几乎都用了这些模式。自从接触了一次阿里的公众号发的一次文章关于 DDD的使用 以后&#xff0c;就逐渐接触了策略模式。现在在项目中运用最多的也是这几种设计模式了…...

Windows + Git + TortoiseGit + Github

一、下载Git&#xff08;Git For Windows&#xff09; 1.1. Git下载地址&#xff1a;https://gitforwindows.org/ 1.2. 默认安装即可&#xff08;包名&#xff1a;Git-2.42.0.2-64-bit.exe&#xff09; 二、下载TortoiseGit 2.1.TortoiseGit下载地址&#xff1a;http://tortoi…...

MySQL数据库索引练习

1.学生表&#xff1a;Student (Sno, Sname, Ssex , Sage, Sdept) 学号&#xff0c;姓名&#xff0c;性别&#xff0c;年龄&#xff0c;所在系 Sno为主键 课程表&#xff1a;Course (Cno, Cname,) 课程号&#xff0c;课程名 Cno为主键 学生选课表&#xff1a;SC (Sno, Cno, Scor…...

mysql面试题10:MySQL中有哪几种锁?表级锁、行级锁、页面锁区别和联系?

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:Mysql中有哪几种锁? 在MySQL中,主要有以下几种类型的锁: 共享锁(Shared Lock):也称为读锁。多个事务可以同时持有共享锁,可以读取但不能修…...

ctfshow—1024系列练习

1024 柏拉图 有点像rce远程执行&#xff0c;有四个按钮&#xff0c;分别对应四份php文件&#xff0c;开始搞一下。一开始&#xff0c;先要试探出 文件上传到哪里&#xff1f; 怎么读取上传的文件&#xff1f; 第一步&#xff1a;试探上传文件位置 直接用burp抓包&#xff0c;…...

javaWeb学生信息管理

一、引言 学生信息管理系统是基于Java Web技术开发的一个全栈应用&#xff0c;用于管理学生的基本信息。本系统采用Eclipse作为开发工具&#xff0c;Navicat用于MySQL数据库管理&#xff0c;运行在JDK1.8、Tomcat9.0、MySQL8.0环境下。前端采用JavaScript、jQuery、Bootstrap4…...

玩转gpgpu-sim 04记—— __cudaRegisterBinary() of gpgpu-sim 到底做了什么

官方文档&#xff1a; GPGPU-Sim 3.x Manual __cudaRegisterBinary(void*) 被执行到的代码逻辑如下&#xff1a; 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&#xff1a;开源世界的强大数据库 在当今数字化时代&#xff0c;数据是组织的最宝贵资源之一。数据库管理系统&#xff08;DBMS&#xff09;扮演着关键角色&#xff0c;帮助企业存储、管理和分析数据。PostgreSQL&#xff0c;作为一款开源的高级关系型数据库…...

基本的五大排序算法

目录&#xff1a; 一&#xff0c;直接插入算法 二&#xff0c;希尔排序算法 三&#xff0c;选择排序 四&#xff0c;堆排序 五&#xff0c;冒泡排序算法 简介&#xff1a; 排序算法目前是我们最常用的算法之一&#xff0c;据研究表明&#xff0c;目前排序占用计算机CPU的时…...

封装api的理解

1.基地址(baseUrl) (1).测试环境 用于测试环境的运行 (2).正式环境 用于正式环境的运行 2.拦截器 1.请求拦截器 (1)成功的回调 做的事情:例如在请求头header里面加入toekn。 (2)失败的回调 直接返回失败的结果: return promise.reject(error) 2.响应拦截器 (1)成功的回…...

Unity实现设计模式——命令模式

Unity实现设计模式——命令模式 推荐一个Unity学习设计模式很好的GitHub地址&#xff1a;https://github.com/QianMo/Unity-Design-Pattern 有非常多的Star 一、介绍 命令模式使得请求的发送者与请求的执行者之间消除耦合&#xff0c;让对象之间的调用关系更加灵活。在命令模…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...