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

蓝桥杯每日一题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题库 题目描述 题目分析 对于这一我们需要有前缀知识完全背包 完全背包的朴素写法&#xff1a; #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实例:简单线性回归的训练和反向传播解析

文章目录 &#x1f966;引言&#x1f966;什么是反向传播&#xff1f;&#x1f966;反向传播的实现&#xff08;代码&#xff09;&#x1f966;反向传播在深度学习中的应用&#x1f966;链式求导法则&#x1f966;总结 &#x1f966;引言 在神经网络中&#xff0c;反向传播算法…...

Arcgis提取玉米种植地分布,并以此为掩膜提取遥感影像

Arcgis提取玉米种植地分布上&#xff0c;并以此为掩膜提取遥感影像 一、问题描述 因为之前反演是整个研究区&#xff0c;然而土地利用类型有很多类&#xff0c;只在农田或者植被上进行反演&#xff0c;需要去除水体、建筑等其他类型&#xff0c;如何处理得到下图中只有耕地类…...

软件工程与计算总结(四)项目管理基础

目录 一.项目和项目管理 二.团队组织与管理 三.软件质量保障 四.软件配置管理 五.项目实践 一.项目和项目管理 1.软件开发远不是纯粹的编程&#xff0c;随着软件规模的增长&#xff0c;软件开发活动也变得越来越复杂~ 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搭建流媒体服务&#xff0c;利用ffmpeg进行推流&#xff0c;在pc上使用vlc media进行拉流播放。 1.rtmp流媒体服务框架图 2.nginx配置 下载&#xff1a;wge…...

IDEA 将一个普通Java工程转化为maven工程

打开IntelliJ IDEA并打开Java工程。 在项目窗口中&#xff0c;右键单击项目名称&#xff0c;选择“Add Framework Support”。 在弹出的窗口中&#xff0c;选择“Maven”。 在“Maven Information”窗口中&#xff0c;填写Group Id、Artifact Id和Version等基本信息。 点击…...

linux下的永久保存行号

linux下的永久保存行号 1.首先 这里是引用 输入命令&#xff1a;vi ~/.vimrc 其次 这里是引用 输入命令 set number...

92岁高龄的创始人张忠谋谈台积电发展史

一、张忠谋和台积电 在台北一间办公室里&#xff0c;张忠谋最近拿出一本印有彩色图案的旧书。它的标题是《VLSI 系统导论》&#xff0c;这是一本研究生水平的教科书&#xff0c;描述了计算机芯片设计的复杂性。92岁的张先生满怀敬意地举起它。 92岁高龄的台积电创始人张忠谋 “…...

【VIM】VIm初步使用

玩转Vim-从放弃到入门_哔哩哔哩_bilibili...

教育类《中学政史地》收稿方向-投稿邮箱

教育类《中学政史地》收稿方向-投稿邮箱 《中学政史地》收稿方向&#xff1a;中学政治、历史、地理类稿件 《中学政史地》创办于1987年&#xff0c;是我国唯一一份集中学政治、历史、地理三门学科为一体的综合性月刊。每月两期&#xff0c;分初中版和高中版。以服务学生、服务…...

数据库的备份与恢复

数据备份的重要性 备份的主要目的是灾难恢复。 在生产环境中&#xff0c;数据的安全性至关重要。 任何数据的丢失都可能产生严重的后果。 造成数据丢失的原因&#xff1a; 程序错误人为操作错误运算错误磁盘故障灾难&#xff08;如火灾、地震&#xff09;和盗窃 数据库备份…...

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 函数指针

就像指针可以指向一般变量、数组、结构体那样&#xff0c;指针也可以指向函数。 函数指针的主要用途是向其他函数传递“回调”&#xff0c;或者模拟类和对象。 形式如下&#xff1a; int (*POINTER_NAME)(int a, int b) 这类似于指向数组的指针可以表示所指向的数组。指向函数…...

zkVM设计性能分析

1. 引言 本文主要参考&#xff1a; 2023年9月ZKSummit10 Wei Dai 1k(x) & Terry Chung 1k(x)分享视频 ZK10: Analysis of zkVM Designs - Wei Dai & Terry Chung 当前有各种zkVM&#xff0c;其设计思想各有不同&#xff0c;且各有取舍&#xff0c;本文重点对现有各z…...

调用gethostbyname实现域名解析(附源码)

VC常用功能开发汇总&#xff08;专栏文章列表&#xff0c;欢迎订阅&#xff0c;持续更新...&#xff09;https://blog.csdn.net/chenlycly/article/details/124272585C软件异常排查从入门到精通系列教程&#xff08;专栏文章列表&#xff0c;欢迎订阅&#xff0c;持续更新...&a…...

面向无线传感器网络WSN的增强型MODLEACH设计与仿真(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

前端页面初步开发

<template><div><el-card class"box-card" style"height: 620px"><el-input v-model"query.name" style"width:200px" placeholder"请输入用户姓名"></el-input>&nbsp&nbsp&nbsp…...

【赠书活动第3期】《构建新型网络形态下的网络空间安全体系》——用“价值”的视角来看安全

目录 一、内容简介二、读者受众三、图书目录四、编辑推荐五、获奖名单 一、内容简介 经过30多年的发展&#xff0c;安全已经深入到信息化的方方面面&#xff0c;形成了一个庞大的产业和复杂的理论、技术和产品体系。 因此&#xff0c;需要站在网络空间的高度看待安全与网络的…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...

C# winform教程(二)----checkbox

一、作用 提供一个用户选择或者不选的状态&#xff0c;这是一个可以多选的控件。 二、属性 其实功能大差不差&#xff0c;除了特殊的几个外&#xff0c;与button基本相同&#xff0c;所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...