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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/148183.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Redis分页+多条件模糊查询组合实现思路

Redis是一个高效的内存数据库&#xff0c;它支持包括String、List、Set、SortedSet和Hash等数据类型的存储&#xff0c;在Redis中通常根据数据的key查询其value值&#xff0c;Redis没有模糊条件查询&#xff0c;在面对一些需要分页、排序以及条件查询的场景时(如评论&#xff0…

基于SSM的健身房管理系统

基于SSM的健身房管理系统的设计与实现 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringSpringMVCMyBatis工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 【主要功能】 角色&#xff1a;管理员、用户 查看健身课程列表、新闻公告查看、推荐课程、购买…

《机器学习实战》学习记录-ch2

PS: 个人笔记&#xff0c;建议不看 原书资料&#xff1a;https://github.com/ageron/handson-ml2 2.1数据获取 import pandas as pd data pd.read_csv(r"C:\Users\cyan\Desktop\AI\ML\handson-ml2\datasets\housing\housing.csv")data.head() data.info()<clas…

【Leetcode】 131. 分割回文串

给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 示例 1&#xff1a; 输入&#xff1a;s "aab" 输出&#xff1a;[["a","a"…

Spring Cloud Zuul 基本原理

Spring Cloud Zuul 底层是基于Servlet实现的&#xff0c;核心是通过一系列的ZuulFilter来完成请求的转发。 1、核心组件注册 1.1. EnableZuulProxy注解 启用Zuul作为微服务网关&#xff0c;需要在Application应用类加上EnableZuulProxy注解&#xff0c;而该注解核心是利用Im…

Web版Photoshop来了,用到了哪些前端技术?

经过 Adobe 工程师多年来的努力&#xff0c;并与 Chrome 等浏览器供应商密切合作&#xff0c;通过 WebAssembly Emscripten、Web Components Lit、Service Workers Workbox 和新的 Web API 的支持&#xff0c;终于在近期推出了 Web 版 Photoshop&#xff08;photoshop.adobe…

Qt+openCV学习笔记(十六)Qt6.6.0rc+openCV4.8.1+emsdk3.1.37编译静态库

前言&#xff1a; 有段时间没来写文章了&#xff0c;趁编译库的空闲&#xff0c;再写一篇记录文档 WebAssembly的发展逐渐成熟&#xff0c;即便不了解相关技术&#xff0c;web前端也在不经意中使用了相关技术的库&#xff0c;本篇文档记录下如何编译WebAssembly版本的openCV&…

区块链3.0时代 基于GoMars构建的新概念TravelFi能否注入新力量?

区块链技术进入3.0时代 后疫情时代&#xff0c;全球数字化进程不断加快&#xff0c;世界范围内的移动通信、互联网技术及各类数字化应用的社会普及率也正在快速提升&#xff0c;疫情推动了互联网经济的增长&#xff0c;也让数字经济的价值开始显现。 数字经济一词的由来至今已经…

网络协议--概述

1.2 分层 网络协议通常分不同层次进行开发&#xff0c;每一层分别负责不同的通信功能。一个协议族&#xff0c;比如TCP/IP&#xff0c;是一组不同层次上的多个协议的组合。TCP/IP通常被认为是一个四层协议系统&#xff0c;如图1-1所示。 每一层负责不同的功能&#xff1a; 1.…

objective-c 基础学习

目录 第一节&#xff1a;OC 介绍 ​​第二节&#xff1a;Fundation 框架 ​第三节&#xff1a;NSLog 相对于print 的增强 ​第四节&#xff1a;NSString ​第五节&#xff1a;oc新增数据类型 第六节&#xff1a; 类和对象 ​类的方法的声明与实现 ​第七节&#xff1a;类…

Linux信号解析

文章目录 Linux信号概念信号种类Linux信号产生异步 LInux信号阻塞递达、未决、阻塞、忽略信号集操作函数阻塞信号集操作函数未决信号集操作函数 Linux信号捕捉signal函数sigaction函数 总结 Linux信号概念 信号在我们的生活中无处不在&#xff0c;常见的如电话铃声&#xff0c…

国庆10.4

QT实现TCP服务器客户端 服务器 头文件 #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTcpServer> //服务器头文件 #include <QTcpSocket> //客户端头文件 #include <QList> //链表容器 #include <QMe…

【C 语言进阶(12)】动态内存管理笔试题

文章目录 题目 1题目 2题目 3题目 4 题目 1 运行 Test 函数后的结果是什么&#xff1f; void GetMemory(char* p) {p (char*)malloc(100); }void Test(void) {char* str NULL;GetMemory(str);strcpy(str, "hello world");printf(str); }代码结果 程序崩溃。 代…

C++ YAML使用

C++工程如何使用YAML-cpp 一、前期准备工作 1、已安装minGW、cmake、make等本地工具。 2、下载YAML-cpp第三方开源代码(一定要下载最新的release版本,不然坑很多)。 3、生成YAML-cpp静态库 (1)在yaml-cpp-master下建立build文件夹; (2)在该文件夹下生成MakaFile文…

C++入门-day01

一、认识C C融合了三种不同的编程方式 C代表的过程性语言在C基础上添加的类、结构体puls代表的面向对象语言C模板支持泛型编程 C完全兼容C的特性 Tips&#xff1a;侯捷老师提倡的Modren C是指C11、C14、C17和C20这些新标准所引入的一系列新特性和改进。在我们练习的时候也应当去…

Blender 之创建一个简单的笔筒

文章目录 成品图实现步骤 你是不是想创建一个笔筒捏&#xff1f; follow me! 成品图 实现步骤 先添加一个柱体 选中柱体&#xff0c;然后按tab 进入编辑模式 切换到面模式 &#xff08;可以按主键盘的 3 键&#xff09; 分别选中上下面&#xff0c;鼠标右键&#xff0c;选…

BL808学习日志-2-LVGL for M0 and D0

一、lvgl测试环境 对拿到的M1S_DOCK开发板进行开发板测试&#xff0c;博流的官方SDK是支持M0和D0两个内核都进行测试的&#xff1b;但是目前只实现了M0的LVGLBenchmark&#xff0c;测试D0内核中发现很多莫名其妙的问题。一会详细记录。 使用的是开发板自带的SPI显示屏&#xff…

【软考】4.2 关系代数/函数依赖/范式

《 关系代数 》 表和表之间的逻辑运算 笛卡尔积&#xff1a;S1 x S2 投影&#xff1a;π&#xff1b;选择某一列&#xff08;属性&#xff09;&#xff1b;一个关系R的投影操作结果也是一个关系&#xff0c;记作Πa&#xff0c;它由从关系R中选出的A列元素构成&#xff1b;选择…

隐私交易成新刚需,Unijoin 凭什么优势杀出重围?

随着区块链技术的普及和发展&#xff0c;全球加密货币用户在持续增长&#xff0c;根据火币研究院公布的数据&#xff0c;2022年全球加密用户已达到 3.2亿人&#xff0c;目前全球人口总数超过了 80亿&#xff0c;加密货币用户渗透率已达到了 4%。 尤其是在 2020 年开启的 DeFi 牛…

机器学习7:逻辑回归

一、说明 逻辑回归模型是处理分类问题的最常见机器学习模型之一。二项式逻辑回归只是逻辑回归模型的一种类型。它指的是两个变量的分类&#xff0c;其中概率用于确定二元结果&#xff0c;因此“二项式”中的“bi”。结果为真或假 — 0 或 1。 二项式逻辑回归的一个例子是预测人…