蓝桥杯每日一题2023.10.5
3420. 括号序列 - AcWing题库
题目描述

题目分析
对于这一我们需要有前缀知识完全背包
完全背包的朴素写法:
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, v[N], w[N], f[N][N];
int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++)cin >> v[i] >> w[i];for(int i = 1; i <= n; i ++){for(int j = 0; j <= m; j ++){for(int k = 0; k * v[i] <= j; k ++){f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);}}}cout << f[n][m] << '\n';return 0;
}
经行优化:
f[i][j] = f[i - 1][j - v[i] * k] + w[i] * k
f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, f[i - 1][j - 3v] + 3w, ...)
f[i][j - v] = max( f[i - 1][j - v], f[i - 1][j - 2v] + w, f[i - 1][j - 3v] + 2w, ...)
f[i][j] = max(f[i - 1][j], f[i][j - v] + w)
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, v[N], w[N], f[N][N];
int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++)cin >> v[i] >> w[i];for(int i = 1; i <= n; i ++){for(int j = 0; j <= m; j ++){for(int k = 0; k * v[i] <= j; k ++){f[i][j] = f[i - 1][j];if(j >= v[i])f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);}}}cout << f[n][m] << '\n';return 0;
}
首先由题意知我们左右括号的数量必须相等,对于任意前缀的左括号的数量必须大于等于有括号的数量(如果小于则此处必定需要添加括号)
我们可以分为两种方案使其独立存在,一种是只添加左括号,一种是只添加右括号,这两种方案各进行一次,将方案数相乘则为总方案数,对于左右进行的操作只需用同一代码即可,我们可以只写对左括号进行操作,对于右括号操作我们只需要将字符串翻转即可实现操作
使用动态规划来记录方案数
f[i][j] :只考虑前i部分,左括号比右括号多j 个的所有方案的集合(不同数量的左括号的方案数)
1.若s[i] == '(' f[i][j] = f[i - 1][j - 1](考虑前i - 1部分时,左括号数量比右括号数量多j - 1个,那么第i部分左括号就比右括号多j个)
2.若s[i] == ')' f[i][j] = f[i - 1][j + 1] + f[i - 1][j] + ... + f[i - 1][0](考虑前i - 1部分左括号数量最多比右括号数量多j + 1个,才能在第i部分通过添加或者不加左括号使左括号的数量比右括号的数量多j个)注:这里类似于完全背包的优化:f[i][j] = f[i - 1][j + 1] + f[i][j - 1],考虑越界问题,f[i][0]特判(j == 0,j - 1 = -1越界)f[i][0]可以考虑前i - 1部分左括号数和右括号数相等 和 左括号数比右括号数多一个的和
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010, mod = 1e9 + 7;
char s[N];
int n;
ll f[N][N];
ll work()
{memset(f, 0, sizeof f);f[0][0] = 1;for(int i = 1; i <= n; i ++){if(s[i] == '('){for(int j = 1; j <= n; j ++)f[i][j] = f[i - 1][j - 1];}else{f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;for(int j = 1; j <= n; j ++)f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod;}}for(int i = 0; i <= n; i ++){if(f[n][i])return f[n][i];}return -1;
}
int main()
{cin >> s + 1;n = strlen(s + 1);ll l = work();reverse(s + 1, s + n + 1);for(int i = 1; i <= n; i ++){if(s[i] == '(')s[i] = ')';else s[i] = '(';}ll r = work();cout << l * r % mod;return 0;
}相关文章:
蓝桥杯每日一题2023.10.5
3420. 括号序列 - AcWing题库 题目描述 题目分析 对于这一我们需要有前缀知识完全背包 完全背包的朴素写法: #include<bits/stdc.h> using namespace std; const int N 1010; int n, m, v[N], w[N], f[N][N]; int main() {cin >> n >> m;fo…...
PyTorch实例:简单线性回归的训练和反向传播解析
文章目录 🥦引言🥦什么是反向传播?🥦反向传播的实现(代码)🥦反向传播在深度学习中的应用🥦链式求导法则🥦总结 🥦引言 在神经网络中,反向传播算法…...
Arcgis提取玉米种植地分布,并以此为掩膜提取遥感影像
Arcgis提取玉米种植地分布上,并以此为掩膜提取遥感影像 一、问题描述 因为之前反演是整个研究区,然而土地利用类型有很多类,只在农田或者植被上进行反演,需要去除水体、建筑等其他类型,如何处理得到下图中只有耕地类…...
软件工程与计算总结(四)项目管理基础
目录 一.项目和项目管理 二.团队组织与管理 三.软件质量保障 四.软件配置管理 五.项目实践 一.项目和项目管理 1.软件开发远不是纯粹的编程,随着软件规模的增长,软件开发活动也变得越来越复杂~ 2.软件项目就是要将所有的软件开发活动组织起来&#…...
【Python】datetime 库
# timedelta(days, seconds, microseconds,milliseconds, minutes, hours, weeks) 默认按顺序传递参数 # 主要介绍 datetime.datetime 类 # 引入 from datetime import datetime today datetime.now() # 获取当前时间 2023-10-05 15:58:03.218651 today1 datetime.utcnow() #…...
从0开始python学习-28.selenium 需要图片验证的登录
url https://test.com/login driver.get(url) # 获取登录页面需要输入账号密码进行模拟登录操作 user driver.find_element(By.XPATH,//*[id"login"]/div[2]/div/form[2]/div[2]/div/div/input).send_keys(username) pwd driver.find_element(By.XPATH,//*[id&qu…...
Nginx搭建Rtmp流媒体服务,并使用Ffmpeg推流
文章目录 1.rtmp流媒体服务框架图2.nginx配置3.配置nginx4.使用ffmpeg推流5.实时推摄像头流 本项目在开发板上使用nginx搭建流媒体服务,利用ffmpeg进行推流,在pc上使用vlc media进行拉流播放。 1.rtmp流媒体服务框架图 2.nginx配置 下载:wge…...
IDEA 将一个普通Java工程转化为maven工程
打开IntelliJ IDEA并打开Java工程。 在项目窗口中,右键单击项目名称,选择“Add Framework Support”。 在弹出的窗口中,选择“Maven”。 在“Maven Information”窗口中,填写Group Id、Artifact Id和Version等基本信息。 点击…...
linux下的永久保存行号
linux下的永久保存行号 1.首先 这里是引用 输入命令:vi ~/.vimrc 其次 这里是引用 输入命令 set number...
92岁高龄的创始人张忠谋谈台积电发展史
一、张忠谋和台积电 在台北一间办公室里,张忠谋最近拿出一本印有彩色图案的旧书。它的标题是《VLSI 系统导论》,这是一本研究生水平的教科书,描述了计算机芯片设计的复杂性。92岁的张先生满怀敬意地举起它。 92岁高龄的台积电创始人张忠谋 “…...
【VIM】VIm初步使用
玩转Vim-从放弃到入门_哔哩哔哩_bilibili...
教育类《中学政史地》收稿方向-投稿邮箱
教育类《中学政史地》收稿方向-投稿邮箱 《中学政史地》收稿方向:中学政治、历史、地理类稿件 《中学政史地》创办于1987年,是我国唯一一份集中学政治、历史、地理三门学科为一体的综合性月刊。每月两期,分初中版和高中版。以服务学生、服务…...
数据库的备份与恢复
数据备份的重要性 备份的主要目的是灾难恢复。 在生产环境中,数据的安全性至关重要。 任何数据的丢失都可能产生严重的后果。 造成数据丢失的原因: 程序错误人为操作错误运算错误磁盘故障灾难(如火灾、地震)和盗窃 数据库备份…...
string类的模拟实现(万字讲解超详细)
目录 前言 1.命名空间的使用 2.string的成员变量 3.构造函数 4.析构函数 5.拷贝构造 5.1 swap交换函数的实现 6.赋值运算符重载 7.迭代器部分 8.数据容量控制 8.1 size和capacity 8.2 empty 9.数据修改部分 9.1 push_back 9.2 append添加字符串 9.3 运算符重载…...
C 函数指针
就像指针可以指向一般变量、数组、结构体那样,指针也可以指向函数。 函数指针的主要用途是向其他函数传递“回调”,或者模拟类和对象。 形式如下: int (*POINTER_NAME)(int a, int b) 这类似于指向数组的指针可以表示所指向的数组。指向函数…...
zkVM设计性能分析
1. 引言 本文主要参考: 2023年9月ZKSummit10 Wei Dai 1k(x) & Terry Chung 1k(x)分享视频 ZK10: Analysis of zkVM Designs - Wei Dai & Terry Chung 当前有各种zkVM,其设计思想各有不同,且各有取舍,本文重点对现有各z…...
调用gethostbyname实现域名解析(附源码)
VC常用功能开发汇总(专栏文章列表,欢迎订阅,持续更新...)https://blog.csdn.net/chenlycly/article/details/124272585C软件异常排查从入门到精通系列教程(专栏文章列表,欢迎订阅,持续更新...&a…...
面向无线传感器网络WSN的增强型MODLEACH设计与仿真(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
前端页面初步开发
<template><div><el-card class"box-card" style"height: 620px"><el-input v-model"query.name" style"width:200px" placeholder"请输入用户姓名"></el-input>   …...
【赠书活动第3期】《构建新型网络形态下的网络空间安全体系》——用“价值”的视角来看安全
目录 一、内容简介二、读者受众三、图书目录四、编辑推荐五、获奖名单 一、内容简介 经过30多年的发展,安全已经深入到信息化的方方面面,形成了一个庞大的产业和复杂的理论、技术和产品体系。 因此,需要站在网络空间的高度看待安全与网络的…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
uniapp 小程序 学习(一)
利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 :开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置,将微信开发者工具放入到Hbuilder中, 打开后出现 如下 bug 解…...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究
摘要:在消费市场竞争日益激烈的当下,传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序,探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式,分析沉浸式体验的优势与价值…...
数据库——redis
一、Redis 介绍 1. 概述 Redis(Remote Dictionary Server)是一个开源的、高性能的内存键值数据库系统,具有以下核心特点: 内存存储架构:数据主要存储在内存中,提供微秒级的读写响应 多数据结构支持&…...
