2023-08-18力扣每日一题
链接:
1388. 3n 块披萨
题意:
一个长度3n的环,选n次数字,每次选完以后相邻的数字会消失,求选取结果最大值
解:
这波是~~(ctrl)CV工程师了~~
核心思想是选取n个不相邻的元素一定合法,我推不出来,猜一猜倒是可以O.o
DP[i][j]
表示从[0,i]
中选取j
个数字的最大值
初始条件,我们可以确定,如果选择0个数字j==0
则结果为0;如果j<i+1
,,则要在不足的数字中进行选取,我们设为0(官方是设为INT_MIN,我写了0好像也没事,可能是数据弱了?);由于思想中只对相邻数字做判断,所以我们提供[0,0]和[0,1]
选取1个数字的值作为DP的初始条件之一,即dp[0][1]=temp[0] 和 dp[1][1]=max(temp[0],temp[1])
剩下的就很简单了,状态转移就是从小的范围推导出大的范围,少的选取推导出多的选取,每个DP[I][J]
只需要判断I
选不选就行
特别注意的是,由于整体成环状,所以分别对去掉头和去掉尾进行一次DP(因为只考虑相邻)
只要能推出取n个不相邻的数字就能满足题意就很好写了
实际代码:
#include<bits/stdc++.h>
using namespace std;
int solve(vector<int>& temp)
{int num=temp.size(),need=(num+1)/3;vector<vector<int>>dp(num,vector<int>(need+1,0));dp[0][1]=temp[0];dp[1][1]=max(temp[0],temp[1]);for(int i=2;i<num;i++){for(int j=1;j<=need;j++){dp[i][j] = max(dp[i - 1][j],dp[i - 2][j - 1]+temp[i]);}}return dp[num-1][need];
}
int maxSizeSlices(vector<int>& slices)
{int lg=slices.size();vector<int> v1(slices.begin() + 1, slices.end());vector<int> v2(slices.begin(), slices.end() - 1);return max(solve(v1),solve(v2));
}
int main()
{vector<int> slices;int slice;while(cin>>slice) slices.push_back(slice);int ans=maxSizeSlices(slices);cout<<ans<<endl;return 0;
}
限制:
1 <= slices.length <= 500
slices.length % 3 == 0
1 <= slices[i] <= 1000
相关文章:
2023-08-18力扣每日一题
链接: 1388. 3n 块披萨 题意: 一个长度3n的环,选n次数字,每次选完以后相邻的数字会消失,求选取结果最大值 解: 这波是~~(ctrl)CV工程师了~~ 核心思想是选取n个不相邻的元素一定…...
mac M1安装opencv方法及类型报错解决
安装opencv: pip install opencv-python pip install --user opencv-contrib-python pip install opencv-python 4.5.2.54 numpy 1.25.2 安装过程中报错如下: python-类型错误:“numpy._DTypeMeta”对象不可下标 TypeError: ‘numpy._DTypeMeta’ obje…...
Screen终端管理工具
文章目录 Screen终端管理工具背景nohup介绍screen介绍安装screen查看终端新建终端退出终端进入终端删除会话帮助命令 总结 Screen终端管理工具 背景 对大佬只有膜拜,可能永远无法超越,在工作交接中大佬用到了一个screen启动了程序,这是什么…...
【python自动化办公】PysimpleGUI官网案例全部项目代码文件及运行截图
PysimpleGUI官网案例全部项目代码文件及运行截图 0 项目文件整体预览窗口1 pysimpleGUI下面所有元素2 pysimpleGUI下面所有元素示例3 加载多GIF图片4 使用PIL进行动态图片加载5 自动保存关闭时窗口位置信息6 绘制柱状图7 图像编码18 图像编码29 无边界窗口10 设置图片按钮11 按…...

9.处理this和防抖、节流
9.1 this指向-普通函数 普通函数的调用方式决定了this的值,即【谁调用this的值 指向谁】 普通函数没有明确调用者时this值为window,严格模式下没有调用者时this的值为undefined 9.2 this指向-箭头函数 箭头函数中的this与普通函数完全不同࿰…...
Spark操作Hive表幂等性探索
前言 旁边的实习生一边敲着键盘一边很不开心的说:做数据开发真麻烦,数据bug排查太繁琐了,我今天数据跑的有问题,等我处理完问题重新跑了代码,发现报表的数据很多重复,准备全部删了重新跑。 我:你的数据操作具备幂等性吗? 实习生:啥是幂等性?数仓中的表还要考虑幂等…...

【可变形卷积3】 DCNv2 安装
使用RTM3D 代码,CenterTrack代码需要用DCN 1、安装DCNv2 (1)github上最新版的DCNv2源码在"https://github.com/CharlesShang/DCNv2",但是该版本源码不支持PyTorch1.7,如果使其支持PyTorch1.7需要做以下修改…...

归并排序 与 计数排序
目录 1.归并排序 1.1 递归实现归并排序: 1.2 非递归实现归并排序 1.3 归并排序的特性总结: 1.4 外部排序 2.计数排序 2.1 操作步骤: 2.2 计数排序的特性总结: 3. 7种常见比较排序比较 1.归并排序 基本思想: 归并排序(MERGE-SORT)是建立在归并操作上的一种…...
机器学习之逻辑回归
import numpy as np import pandas as pd from sklearn.model_selection import train_test_split from sklearn.preprocessing import StandardScaler from sklearn.linear_model import LogisticRegression # 获得数据 names[Sample code number,Clump Thickness,Uniformity…...

操作符详解上(非常详细)
目录 二进制介绍二进制2进制转10进制10进制转2进制数字2进制转8进制和16进制2进制转8进制2进制转16进制 原码、反码、补码移位操作符左移操作符右移操作符 位操作符:&、|、^逗号表达式 二进制介绍 在初学计算机时我们常常会听到2进制、8进制、10进制、16进制……...

React 高阶组件(HOC)
React 高阶组件(HOC) 高阶组件不是 React API 的一部分,而是一种用来复用组件逻辑而衍生出来的一种技术。 什么是高阶组件 高阶组件就是一个函数,且该函数接受一个组件作为参数,并返回一个新的组件。基本上,这是从 React 的组成…...

【NepCTF2023】复现
文章目录 【NepCTF2023】复现MISC与AI共舞的哈夫曼codesc语言获取环境变量 小叮弹钢琴陌生的语言你也喜欢三月七么Ez_BASIC_IImisc参考 WEBez_java_checkinPost Crad For You独步天下配置环境独步天下-镜花水月环境变量提权 独步天下-破除虚妄总结 独步天下-破除试炼_加冕成王知…...
大文件切片上传
创建组件:创建一个组件用于处理文件上传,命名为Upload.vue。 <template><div><input type"file" change"handleFileChange" /><button click"startUpload">开始上传</button></div> …...

ubuntu切换python版本
在没有安装类似anoconda的管理工具的时候,我们常常会被Ubuntu下的Python版本切换问题所头疼。 可以使用update-alternatives工具进行python版本的任意切换 当使用update-alternatives工具来切换Ubuntu系统上的Python版本时,您实际上是在系统范围内选择…...
docker 安装 elasticsearch、kibana 7.4.2
切换root 用户 su root 拉起镜像 docker pull elasticsearch:7.4.2 docker pull kibana:7.4.2 #1、创建Elasticsearch配置文件夹 mkdir -p /mydata/elasticsearch/config #2、创建Elasticsearch数据文件夹 mkdir -p /mydata/elasticsearch/data #3、创建Elasticsearch插件…...
【es6】函数参数设置默认值
1、es6之前的函数参数默认值写法 1.1、使用短路或||的写法 当y为空时,y判断为false ,走||右边的,所以y world;当y不为空时,y判断为true,不需要再运行||右边的,所以 y y function log(x, y) {y y || W…...

Pytest和Unittest测试框架的区别?
如何区分这两者,很简单unittest作为官方的测试框架,在测试方面更加基础,并且可以再次基础上进行二次开发,同时在用法上格式会更加复杂;而pytest框架作为第三方框架,方便的地方就在于使用更加灵活࿰…...
C#基础知识(一)
一、C#程序结构 《1》命名空间的声明(namespace declaration) 《2》一个class 《3》class方法 《4》class属性 《5》一个main方法 《6》语句(statements)&表达式(Expressions) 《7》注释 注:…...

我还不知道?Android组件化插件化模块化
Android组件化、插件化和模块化是针对Android应用程序开发的一种架构设计思想和开发方式。 组件化(Componentization): 组件化是将一个大型的Android应用程序拆分成多个独立的组件(Module),每个组件可以独…...

借助 AI 工具,真的能成为 10x 工程师?
或许你听说过 10x 工程师吗? 如果你问猎头公司 10x 工程师是什么意思,他们可能会说 “生产力”!10x 是指完成任务比别人快 10 倍的工程师。 2019 年,Twitter 上就曾经对 10 x 工程师这一议题有过一次空前热烈的讨论,引…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...

三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...

UE5 音效系统
一.音效管理 音乐一般都是WAV,创建一个背景音乐类SoudClass,一个音效类SoundClass。所有的音乐都分为这两个类。再创建一个总音乐类,将上述两个作为它的子类。 接着我们创建一个音乐混合类SoundMix,将上述三个类翻入其中,通过它管理每个音乐…...

边缘计算网关提升水产养殖尾水处理的远程运维效率
一、项目背景 随着水产养殖行业的快速发展,养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下,而且难以实现精准监控和管理。为了提升尾水处理的效果和效率,同时降低人力成本,某大型水产养殖企业决定…...

如何把工业通信协议转换成http websocket
1.现状 工业通信协议多数工作在边缘设备上,比如:PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发,当设备上用的是modbus从站时,采集设备数据需要开发modbus主站;当设备上用的是西门子PN协议时…...