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 工程师这一议题有过一次空前热烈的讨论,引…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

ios苹果系统,js 滑动屏幕、锚定无效
现象:window.addEventListener监听touch无效,划不动屏幕,但是代码逻辑都有执行到。 scrollIntoView也无效。 原因:这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作,从而会影响…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...

WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...