POJ上的1141题目是Brackets Sequence
输入一个由(、)、[、]四个字符组成的字符串
规定如下的字符串是合格的:
1.空串是合格的;
2.如果S是合格的,那么(S)和[S]也是合格的
3.如果A和B是合格的,那么AB也是合格
对于一个不合格的字符串,总能通过添加一些字符使之成为合格的。
题目要求:输入一个字符串,输出最短合格字符串
Sample Input:
([)]
Sample Output:
()[()]
这个题目还是DP问题,我对于DP问题不是特别熟悉,所以做起来还是有些吃力。而且本题要记录路径
解题思路:
dd[i][j]表示从i到j的字符串转换为合格字符串所需要添加的最少字符数。
显然,如果字符串长度为1,则dd[i][i]=1;
如果字符串形如(S)或者(s'),则dd[i][j]=dd[i+1][j-1]
否则,dd[i][j]=min{dd[i][k]+dd[k+1][j]}
path[i][j]表示从i到j最佳划分的位置,即k值
显然,path[i][i]=i,同时如果形如(S)或[S],规定path[i][j]=-1
注意:1.还是要采用自底向上的方法,否则会超时
2.对于形如(S)或者[S]的字符串,S中间有可能存在')(',此时左右的括号匹配不是最合适,仍然需要划分求解,比较哪种情况下的值最小
#include<stdio.h>
char seq[110]; //输入字符串
int dd[110][110],path[110][110];
//查找路径,当发现seq[i]需要添加字符时
//如果seq[i]是括号时,将其设置为'0'
//seq[i]是中括号时,将其设置为'1'
void printPath(int start,int end,int path[][110]){
int k;
if(start>end)
return;
k=path[start][end];
//可能存在[][]的情况,所以要循环
while(k==-1||k==-2){
if(end-start>1)
{
if(k==-1)
{ start=start+1;end=end-1; }
else
start=start+2;
k=path[start][end];
}
else
return;
}
//递归到了单个字符,设置0和1
if(start==end&&start==k)
{
if(seq[start]=='('||seq[start]==')')
seq[start]='0';
else
seq[start]='1';
}
if(start!=end){
printPath(start,k,path);
printPath(k+1,end,path);
}
}
int main()
{
int len;
int i,j,k;
int temp;
memset(dd,0,sizeof(dd));
gets(seq);
len=strlen(seq);
//初始化
for(i=0;i<len;i++)
{ dd[i][i]=1;path[i][i]=i; }
//i代表步长,即从j开始,长度为i的字符串
//j代表字符串开始位置
//k代表分割位置,范围是(j,j+i)
for(i=1;i<len;i++)
{
for(j=0;j+i<len;j++)
{
dd[j][j+i]=999;
//如果形式为()或[]
if((seq[j]=='('&&seq[j+i]==')')||
(seq[j]=='['&&seq[j+i]==']')){
if((seq[j]=='('&&seq[j+1]==')')||
(seq[j]=='['&&seq[j+1]==']')){
dd[j][j+i]=dd[j+2][j+i];
path[j][j+i]=-2;
}
else{
dd[j][j+i]=dd[j+1][j+i-1];
path[j][j+i]=-1;
}
}
//分割
for(k=j;k<=j+i;k++)
{
temp=dd[j][k]+dd[k+1][j+i];
if(dd[j][j+i]>temp)
{ dd[j][j+i]=temp;path[j][j+i]=k; }
}
}
}
//printf("%d\n",dd[0][len-1]);
printPath(0,len-1,path);
//print path
for(i=0;i<len;i++)
{
if(seq[i]=='0')
printf("()");
else if(seq[i]=='1')
printf("[]");
else
printf("%c",seq[i]);
}
printf("\n");
}
分享到:
相关推荐
串流分屏 - 两台笔记本电脑屏幕共享
tornado-6.3.2-cp38-abi3-musllinux_1_1_x86_64.whl
基于java的银行业务管理系统答辩PPT.pptx
TA_lib库(whl轮子),直接pip install安装即可,下载即用,非常方便,各个python版本对应的都有。 使用方法: 1、下载下来解压; 2、确保有python环境,命令行进入终端,cd到whl存放的目录,直接输入pip install TA_lib-xxxx.whl就可以安装,等待安装成功,即可使用! 优点:无需C++环境编译,下载即用,方便
"Turkish Law Dataset for LLM Finetuning" 是一个专为法律领域预训练的大型语言模型(LLM)微调而设计的数据集。这个数据集包含了大量的土耳其法律文本,旨在帮助语言模型更好地理解和处理土耳其法律相关的查询和文档。 该数据集的特点包括: 专业领域:专注于土耳其法律领域,提供了大量的法律文本和案例,使模型能够深入学习法律语言和术语。 大规模:数据集规模庞大,包含了超过1000万页的法律文档,总计约135.7GB的数据,这为模型提供了丰富的学习材料。 高质量:数据经过清洗和处理,去除了噪声和非句子文本,提高了数据质量,使得模型训练更加高效。 预训练与微调:数据集支持预训练和微调两个阶段,预训练阶段使用了大量的土耳其语网页数据,微调阶段则专注于法律领域,以提高模型在特定任务上的表现。 多任务应用:微调后的模型可以应用于多种法律相关的NLP任务,如法律文本摘要、标题生成、文本释义、问题回答和问题生成等。 总的来说,这个数据集为土耳其法律领域的自然语言处理研究提供了宝贵的资源,有助于推动土耳其语法律技术的发展,并为法律专业人士提供更精准的技术支持。通过微调,
农业信息化服务平台 SSM毕业设计 附带论文 启动教程:https://www.bilibili.com/video/BV1GK1iYyE2B
tornado-6.1b2-cp36-cp36m-manylinux2010_i686.whl
计算机NLP_预训练模型文件
随心淘网管理系统 SSM毕业设计 附带论文 启动教程:https://www.bilibili.com/video/BV1GK1iYyE2B
计算机汇编杂谈-理解其中的原理
基于java的藏区特产销售平台答辩PPT.pptx
本压缩包资源说明,你现在往下拉可以看到压缩包内容目录 我是批量上传的基于SpringBoot+Vue的项目,所以描述都一样;有源码有数据库脚本,系统都是测试过可运行的,看文件名即可区分项目~ |Java|SpringBoot|Vue|前后端分离| 开发语言:Java 框架:SpringBoot,Vue JDK版本:JDK1.8 数据库:MySQL 5.7+(推荐5.7,8.0也可以) 数据库工具:Navicat 开发软件: idea/eclipse(推荐idea) Maven包:Maven3.3.9+ 系统环境:Windows/Mac
安装包
项目经过测试均可完美运行! 环境说明: 开发语言:java jdk:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse
项目经过测试均可完美运行! 环境说明: 开发语言:java jdk:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse
Windows x64 操作系统上安装 Python 3.11 版本对应的dlib库,操作简单,无需pip在下载,再也不怕网络超时等其他不确定错误 使用方法: 1、确保windows x64系统上安装了python,可以用anaconda自带的python 2、确认python版本为3.11版本 3、下载资源解压为dlib-19.24.1-cp311-cp311-win_amd64.whl到本地,cd到对应目录,终端直接输入命令pip install dlib-19.24.1-cp311-cp311-win_amd64.whl 等待安装成功提示就可以用了,非常方便,有使用问题欢迎私信哟!
Jira插件安装包
项目经过测试均可完美运行! 环境说明: 开发语言:java jdk:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse
tornado-6.1b2.tar.gz