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

做网站要写多少行代码/网站推广工作

做网站要写多少行代码,网站推广工作,济南做设计公司网站,包装设计概念题目链接:P8746 [蓝桥杯 2021 省 A] 分果果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 样例1输入: 5 2 6 1 2 7 9 样例1输出: 0 样例2输入: 5 5 6 1 2 7 9 样例2输出: 2 分析:这道题的状态表…

题目链接:P8746 [蓝桥杯 2021 省 A] 分果果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

样例1输入: 

5 2
6 1 2 7 9

样例1输出:

0

样例2输入:

5 5
6 1 2 7 9

样例2输出:

2

分析:这道题的状态表示比较难想:首先我们先考虑一下有哪些东西需要维护:

1.当前分配到哪个小朋友

2.当前分配到的小朋友的糖果最小值

3.当前分配到的小朋友的糖果最大值

4.当前已经分配一次的糖果编号位置

5.当前已经分配两次的糖果编号位置

那么其中我们可以选择一个作为f数组的含义,其余的四个显然都需要枚举。我们可以考虑用f数组存储当前状态分配到的小朋友的糖果的最大值,那么我们就开始枚举剩余四个维度。

设f[i][j][k]表示第i个人取到的最后一个糖果编号是j,第i-1个人取到的最后一个糖果编号小于等于k时的最大重量的最小值

答案就是min(f[m][n][n]-mn),所以我们要在mn一定的情况下尽可能减少f数组的值

首先要枚举的就是分配到的小朋友的糖果的最小值mn,那么我们每次考虑给小朋友分配一段连续的糖果区间就要注意区间和不能小于mn。

那么f[i][j][k]应该怎么更新呢?

首先有f[i][j][k]=f[i][j][k-1],这个无需多言,由于f数组维护的最大值,那么从这个角度也可以看出随着k的增加f数组是非递增的

还有就是第i个人用了前i-1个人中已经分配两次糖果编号的后某个位置开始,不妨设为t

那么就有f[i][j][k]=max(f[i-1][k][t],s[j]-s[t]),s数组是前缀和

但是为了尽可能减少f数组的值,就要使得f[i-1][k][t]和s[j]-s[t]的值都尽可能小,我们可以发现,随着t的增大,这两个值都是在逐渐减小的,但是t也要有一个限制条件,就是因为我们给第i个人分配的糖果区间是[t,j],所以这个区间内的糖果总数是要大于等于最小值mn的,所以这块我们可以

有小伙伴可能会有疑问,为什么不能是从前i-1个人中已经分配一次糖果编号的后一个位置开始呢?这个是包含在上述情况的,因为分配两次糖果编号的位置一定是小于分配一次糖果编号的位置的,所以我们从分配两次糖果编号的位置开始分配总有一次会使得编号位置大于分配一次糖果编号的位置,这个时候原来的分配一次编号的位置就变为了分配两次编号的位置了,那么也就变成上述情况了。

还有就是从上面的分析,我们可以发现每次从分配两次的编号后面的某个位置t开始继续分配,此次分配后的位置都是大于等于分配一次的编号的位置,有没有可能是小于第一次分配编号的位置呢?这个是不可能的,因为如果小于第一次编号分配的位置,那么说明上次分配的区间是包含本次分配的区间的,那么我们完全可以把这两次分配调整为相交但不包含的情况,这样两个区间的最大值一定会减少,由于答案是最大值减去最小值,所以对答案也只会更优

其他就是一些细节上的问题了,可以看下代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=103;
int f[N][N][N],w[N],s[N];
/*
f[i][j][k]表示第i个人取到的最后一个糖果编号是j,第i-1
个人取到的最后一个糖果编号小于等于k时的最大重量的最小值 
*/
bool vis[N*N];//vis[i]记录存在一段区间满足区间和为i
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){scanf("%d",&w[i]);s[i]=s[i-1]+w[i];for(int j=0;j<i;j++)vis[s[i]-s[j]]=true;}int ans=0x3f3f3f3f;for(int mn=1;mn*m<=2*s[n];mn++)//枚举重量最小值 {if(!vis[mn]) continue;//剪枝 memset(f,0x3f,sizeof f);f[0][0][0]=0;for(int i=1;i<=m;i++)//枚举当前更新状态for(int k=0;k<=n;k++)//枚举第i-1个人选的最后一个糖果编号{int id=0;//找到第i-2个人选的最后一个糖果编号for(int j=k;j<=n;j++)//第i个人选的最后一个糖果编号 { if(k>0) f[i][j][k]=f[i][j][k-1];if(s[j]<mn) continue;//每个人选取的最小重量不能小于mn//第i个人选的区间是[id+1,j]while(id<k&&s[j]-s[id]>mn) id++;if(s[j]-s[id]<mn) id--;f[i][j][k]=min(f[i][j][k],max(f[i-1][k][id],s[j]-s[id]));}}ans=min(ans,f[m][n][n]-mn); }printf("%d",ans);return 0;
}

相关文章:

(蓝桥真题)分果果(动态规划)

题目链接&#xff1a;P8746 [蓝桥杯 2021 省 A] 分果果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 样例1输入&#xff1a; 5 2 6 1 2 7 9 样例1输出&#xff1a; 0 样例2输入&#xff1a; 5 5 6 1 2 7 9 样例2输出&#xff1a; 2 分析&#xff1a;这道题的状态表…...

【CSS】CSS 背景设置 ① ( 背景颜色 | 背景图片 | 背景平铺 )

文章目录一、背景颜色1、语法说明2、代码示例二、背景图片1、语法说明2、代码示例三、背景平铺一、背景颜色 1、语法说明 CSS 的背景颜色样式语法 : 默认的背景颜色是 transparent 透明 ; background-color:颜色值;background-color 属性 可以 定义 文本颜色 , 其颜色值有三种…...

uniCloud基础使用

获取openID云函数use strict; exports.main async (event, context) > {//event为客户端上传的参数console.log(event : , event)// jscode2session 微信小程序登录接口&#xff0c;获取openidconst {code} event;// 云函数中如需要请求其他http服务&#xff0c;则使用uni…...

5、Elasticsearch优化

一、Elasticsearch集群配置 1、硬件选择 Elasticsearch的基础是 Lucene &#xff0c;所有的索引和文档数据是存储在本地的磁盘中&#xff0c; 具体的路径可在 ES 的配置文件 ../config/elasticsearch.yml 中配置&#xff0c;如下&#xff1a;磁盘在现代服务器上通常都是瓶颈。…...

地质灾害防治单位资质

地质灾害危险性评估&#xff0c;是指在地质灾害易发区进行工程建设或者编制地质灾害易发区内的国土空间规划时&#xff0c;对建设工程或者规划区遭受山体崩塌、滑坡、泥石流、地面塌陷、地裂缝、地面沉降等地质灾害的可能性和建设工程引发地质灾害的可能性作出评估&#xff0c;…...

打怪升级之发送单个UDP包升级版

目标 1.message的输入由edit_control进行&#xff0c;需要捕获输入。 2.用户的主机地址和发送地址不一样&#xff0c;需要分别设置并绑定。 设计RC外观 必备组件&#xff1a;主机IP与端口&#xff0c;从机IP与端口&#xff0c;消息框&#xff0c;发送&#xff0c;连接按钮。…...

MyBatis开发

MyBatis开发入门搭建MyBatis框架开发环境在自己建的的项目建立个lib文件然后导入包3.两个jar包部署到项目中和为项目添加测试类库4.配置数据库mybatis-config.xml里面的配置&#xff1a;<?xml version"1.0" encoding"UTF-8"?> <!DOCTYPE config…...

excel 数据查询,几个模式化公式请收好

1、一对多查询 所谓一对多&#xff0c;就是符合某个指定条件的有多个结果&#xff0c;要把这些结果都提取出来。 如下图所示&#xff0c;希望根据F2单元格中指定的部门&#xff0c;提取出左侧列表中“生产部”的所有人员姓名。 Excel 2019及以下版本&#xff1a;在H2单元格输…...

Prometheus MySQL 性能监控

一、 介绍 Prometheus 是一种开源的监控系统和时序数据库&#xff0c;旨在收集和处理大量数据并提供可视化、监控警报等功能。它支持多种语言、多种部署方式&#xff0c;并且非常灵活&#xff0c;而且社区支持非常活跃&#xff0c;为用户提供了很多优秀的解决方案。 MySQL 是一…...

刷题记录:牛客NC24261[USACO 2019 Feb G]Cow Land

传送门:牛客 题目描述 Cow Land 总共有 NNN 个不同的景点&#xff08; 2≤N≤1052 \leq N \leq 10^52≤N≤105 &#xff09;。 一共有 n−1n-1n−1 条道路连接任意两个景点&#xff0c;这意味着任意两个景点间只有一条简单路径。 每个景点 iii 都有一个享受值 eie_iei​ &…...

MYSQL开发误区

一、表、列、索引设计误区 1、现象&#xff1a;在线业务系统出现了三张表以上的关联查询 建议&#xff1a;说明业务逻辑在表设计上的实现不合理&#xff0c;需要进行表结构调整&#xff0c;或进行列的冗余&#xff0c;或进行业务改造。 2、现象&#xff1a;大表拆成多张小表之…...

k8s学习之路 | k8s 工作负载 DaemonSet

文章目录1. DaemonSet 基础1.1 什么是 DS1.2 DS 的典型用法1.3 如何编写 DS 资源1.4 DS 示例文件1.5 DS Pod 是如何被调度的1.6 更新 DS1.7 DS 替代方案1.8 DS 工作负载字段描述2. DaemonSet 的使用2.1 每个节点运行一个2.2 DS 更新策略2.3 滚动更新2.4 OnDelete 更新2.6 更新回…...

Javaweb MVC模式和三层架构

MVC 模式和三层架构是一些理论的知识&#xff0c;将来我们使用了它们进行代码开发会让我们代码维护性和扩展性更好。 7.1 MVC模式 MVC 是一种分层开发的模式&#xff0c;其中&#xff1a; M&#xff1a;Model&#xff0c;业务模型&#xff0c;处理业务 V&#xff1a;View&am…...

综合考虑,在客户端程序中嵌入网页程序,首选CefSharp。

综合考虑&#xff0c;在客户端程序中嵌入网页程序&#xff0c;首选CefSharp。 CefSharp 是一种将全功能符合标准的 Web 浏览器嵌入 C# 或 VB.NET 应用程序的简单方法。 https://www.jianshu.com/p/3f50cc747606 WinForm嵌入Web网页的解决方案 Microsoft Edge WebView2诞生较晚…...

【Java基础 下】 030 -- 网络编程

目录 一、什么是网络编程 1、常见的软件架构&#xff08;CS & BS&#xff09; ①、BS架构的优缺点 ②、CS架构的优缺点 2、小结 二、网络编程三要素 1、IP ①、IPv4 ②、IPv6 ③、小结 ④、IPv4的一些细节 ⑤、InetAddress的使用 2、端口号 3、协议 ①、TCP & UDP 三、…...

2021牛客OI赛前集训营-提高组(第三场) T3打拳

2021牛客OI赛前集训营-提高组&#xff08;第三场&#xff09; 题目大意 有2n2^n2n个选手参加拳击比赛&#xff0c;每个人都有一个实力&#xff0c;所有选手的实力用一个111到2n2^n2n的排列表示。 淘汰赛的规则是&#xff1a;每次相邻的两个选手进行比赛&#xff0c;实力值大…...

C++面向对象编程之四:成员变量和成员函数分开存储、this指针、const修饰成员和对象

在C中&#xff0c;成员变量和成员函数是分开存储的&#xff0c;只有非静态成员变量才存储在类中或类的对象上。通过该类创建的所有对象都共享同一个函数#include <iostream> using namespace std;class Monster {public://成员函数不占对象空间&#xff0c;所有对象共享同…...

卷积神经网络(CNN)基础知识

文章目录CNN的组成层卷积层卷积运算卷积的变种分组卷积转置卷积空洞卷积可变形卷积卷积层的输出尺寸和参数量CNN的组成层 在卷积神经⽹络中&#xff0c;⼀般包含5种类型的⽹络层次结构&#xff1a;输入层、卷积层、激活层、池化层和输出层。 输入层&#xff08;input layer&a…...

opencv+python 常见图像预处理

import os import cv2 import numpy as np import pandas as pd from PIL import Image import matplotlib.pylab as plt """图像预处理"""#缩放 #灰度化 #二值化-otsu,自定义&#xff0c;自适应 #均值滤波 #中值滤波 #自定义滤波 #高斯/双倍滤波…...

如何实现一个单例模式

目录 前言 1.饿汉式 2.懒汉式 3.双重检测 4.静态内部类 5.枚举 总结&#xff1a; 前言 单例模式是我们日常开发过程中&#xff0c;遇到的最多的一种设计模式。通过这篇文章主要分享是实现单例的几种实现方式。 1.饿汉式 饿汉式的实现方式比较简单。在类加载的时候&#…...

传输线的物理基础(四):传输线的驱动和返回路径

驱动一条传输线对于将信号发射到传输线的高速驱动器&#xff0c;传输线在传输时间内的输入阻抗将表现得像一个电阻&#xff0c;相当于线路的特性阻抗。鉴于此等效电路模型&#xff0c;我们可以构建驱动器和传输线的电路&#xff0c;并计算发射到传输线中的电压。等效电路如下图…...

Java多态性

文章目录对象的多态性多态的理解举例7.2 多态的好处和弊端7.3 虚方法调用(Virtual Method Invocation)7.4 成员变量没有多态性7.5 向上转型与向下转型7.6 为什么要类型转换呢&#xff1f;7.7 如何向上转型与向下转型7.8 instanceof关键字7.9 复习&#xff1a;类型转换7.10 练习…...

算法拾遗二十七之窗口最大值或最小值的更新结构

算法拾遗二十七之窗口最大值或最小值的更新结构滑动窗口题目一题目二题目三题目四滑动窗口 第一种&#xff1a;R&#xff0c;R右动&#xff0c;数会从右侧进窗口 第二种&#xff1a;L&#xff0c;L右动&#xff0c;数从左侧出窗口 题目一 arr是N&#xff0c;窗口大小为W&…...

【带你搞定第二、三、四层交换机】

​ 01 第二层交换机 OSI参考模型的第二层叫做数据链路层&#xff0c;第二层交换机通过链路层中的MAC地址实现不同端口间的数据交换。 第二层交换机主要功能&#xff0c;就包括物理编址、错误校验、帧序列以及数据流控制。 因为这是最基本的交换技术产品&#xff0c;目前桌面…...

C++基础了解-22-C++ 重载运算符和重载函数

C 重载运算符和重载函数 一、C 重载运算符和重载函数 C 允许在同一作用域中的某个函数和运算符指定多个定义&#xff0c;分别称为函数重载和运算符重载。 重载声明是指一个与之前已经在该作用域内声明过的函数或方法具有相同名称的声明&#xff0c;但是它们的参数列表和定义…...

BatchNormalization

目录 Covariate Shift Internal Covariate Shift BatchNormalization &#xff31;1:BN的原理 Q2:BN的作用 Q3:BN的缺陷 Q4&#xff1a;BN的均值、方差的计算维度 Q5&#xff1a;BN在训练和测试时有什么区别 Q6&#xff1a;BN的代码实现 Covariate Shift 机器学习中&a…...

vue 中安装插件实现 rem 适配

vue 中实现 rem 适配vue 项目实现页面自适应&#xff0c;可以安装插件实现。 postcss-pxtorem 是 PostCSS 的插件&#xff0c;用于将像素单元生成 rem 单位。 autoprefixer 浏览器前缀处理插件。 amfe-flexible 可伸缩布局方案替代了原先的 lib-flexible 选用了当前众多浏览…...

Hadoop学习

1.分布式与集群 hosts文件&#xff1a; 域名映射文件 2.Linux常用命令 ls -a&#xff1a;查看当前目录下所有文件mkdir -p&#xff1a;如果没有对应的父文件夹&#xff0c;会自动创建rm -rf&#xff1a;-f&#xff1a;强制删除 -r&#xff1a;递归删除cp -r&#xff1a;复制文…...

Golang反射源码分析

在go的源码包及一些开源组件中&#xff0c;经常可以看到reflect反射包的使用&#xff0c;本文就与大家一起探讨go反射机制的原理、学习其实现源码 首先&#xff0c;了解一下反射的定义&#xff1a; 反射是指计算机程序能够在运行时&#xff0c;能够描述其自身状态或行为、调整…...

Qt之悬浮球菜单

一、概述 最近想做一个炫酷的悬浮式菜单&#xff0c;考虑到菜单展开和美观&#xff0c;所以考虑学习下Qt的动画系统和状态机内容&#xff0c;打开QtCreator的示例教程浏览了下&#xff0c;大致发现教程中2D Painting程序和Animated Tiles程序有所帮助&#xff0c;如下图所示&a…...