Brackets sequence UVA - 1626 (典型的区间dp+递归打印路径)

2024-04-29 13:32

本文主要是介绍Brackets sequence UVA - 1626 (典型的区间dp+递归打印路径),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

点击链接哦:https://vjudge.net/problem/51187/origin

题目大意:括弧的序列,在一个字符串中只包含" ( " " ) "和“ [ ” “ ] ”,要求空序列为正确的括弧,如果s是正确的序列,那么[s]和(s)也是正确的序列,如果a和b是是正确的序列,那么ab也是正确的序列。

求在给出的字符串基础上要至少添加多少括号才能使得字符序列是正确的。

ps:紫书p278

一开始自己先是用模拟去做的,自己感觉应该能可以模拟出来,而且长度为100也不会超时。但还是考虑的情况太少了,最终再无数的debug中把这个方法给pass掉,还是看了一下紫书的讲解。对于菜鸟的我在短时间内把这个题想到用dp,而且解决确实有点难度。看到转移方程时感觉就是通过题意把情况给遍历一遍一样。但是自己却没想到。

既然是区间dp,那么肯定是二维的了 设dp[i][j]表示至少需要增加的括号个数。

那么在区间i~j上,如果s[i]和s[j]匹配的话,那么最少增加的括号个数就是区间i+1~j-1上的了,那么如果不匹配的话,那就应该是有两个正确的序列组合而成,如果在区间i~j上有一个k,正确的序列是由dp[i][k]+dp[k+1][j]而来,(其实这只是构成正确序列的一种办法,还有其他的办法也能构成最少的正确的序列)。边界:当序列为空时dp[][]=0;当序列只有一个字符是,那么肯定要补上一个,显然dp[i][i]=1;然后用递推求出。在这里有一个关键,就是当s[i]和s[j]匹配的话,还需要通过第二种方案更新吗?如果不同动脑子的话我想为了保险需要比较一下看看能不能更优化。然而书上也是强调必须要在第二种方案上在比较更新一下。比如有序列" [ ] [ ] ",显然左右是匹配的,那么会得到序列“ ] [ ”,显然要多加两个括号,不合情理。

另一个重点就是打印,仍然是递归打印,具体看代码吧;

坑点:注意输入and输出

///典型的区间DP
#include <iostream>
#include <bits/stdc++.h>using namespace std;
string s;
int dp[111][111];
int match(char a,char b)
{if(a=='('&&b==')')return 1;if(a=='['&&b==']')return 1;return 0;
}
void print(int i,int j)
{if(i>j)return ;if(i==j){if(s[i]=='('||s[j]==')')printf("()");else printf("[]");return ;}int ans=dp[i][j];if(match(s[i],s[j])&&ans==dp[i+1][j-1]){printf("%c",s[i]);print(i+1,j-1);printf("%c",s[j]);return ;}for(int k=i;k<j;k++){if(ans==dp[i][k]+dp[k+1][j]){print(i,k);print(k+1,j);return ;}}
}
int main()
{int t;scanf("%d",&t);getchar();while(t--){getchar();getline(cin,s);int n=s.size();for(int i=0;i<n;i++){dp[i+1][i]=0;dp[i][i]=1;}for(int i=n-2;i>=0;i--){for(int j=i+1;j<n;j++){dp[i][j]=n;if(match(s[i],s[j]))dp[i][j]=min(dp[i][j],dp[i+1][j-1]);for(int k=i;k<j;k++){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);}}}print(0,n-1);printf("\n");if(t)printf("\n");}return 0;
}


这篇关于Brackets sequence UVA - 1626 (典型的区间dp+递归打印路径)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/946224

相关文章

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

《Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursion)的问题及解决方案》使用Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursi... 目录解决方案‌1. 使用 @jsonIgnore 忽略一个方向的引用2. 使用 @JsonManagedR

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

Rust中的BoxT之堆上的数据与递归类型详解

《Rust中的BoxT之堆上的数据与递归类型详解》本文介绍了Rust中的BoxT类型,包括其在堆与栈之间的内存分配,性能优势,以及如何利用BoxT来实现递归类型和处理大小未知类型,通过BoxT,Rus... 目录1. Box<T> 的基础知识1.1 堆与栈的分工1.2 性能优势2.1 递归类型的问题2.2

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》:本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm