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");
}
分享到:
相关推荐
这里是两种AC1141的两种代码,解题报告我空间有 http://hi.csdn.net/dongdong331
Brackets文件图标插件 Brackets文件图标插件 Brackets文件图标插件
brackets关于vue的插件 brackets关于vue的插件 brackets关于vue的插件
2023.3.6 版本,找到idea插件安装目录,将此插件里面的intellij-rainbow-brackets-2023.3.6.jar 替换为附件中的jar Rainbowify各种类型的括号(圆形、波浪形、方形、角度) Rainbowify更多语言的变量&使用颜色...
brackets1.9 for linux 提供了deb包
Brackets Emmet插件安装包,下载地址为:https://s3.amazonaws.com/extend.brackets/brackets-emmet/brackets-emmet-1.2.1.zip 但是在国内下载特别的慢,特上传上来分享哈. 安装完成后可修改Emmet插件的快捷键: ...
brackets plugins
因为我在Brackets的插件中心安装Beautify插件老是失败,所以我在网上找原因,找了很多后终于让我找到了,下载这个插件包然后手动安装插件就行了, 我试过可行的。
Brackets用着漂亮的UI,还有许多特色功能,它是一款基于web语言开发的编辑器,在编辑器中按F12会在Chrome浏览器中打开控制台,可以看到Brackets的“内脏”。 本人使用的是Sublime Text,由于熟悉了ST的快捷键,...
Brackets的Emmet插件
Brackets.Release.1.13 Brackets.Release.1.13 Brackets.Release.1.13 Brackets.Release.1.13
Brackets is a modern open-source code editor for HTML, CSS and JavaScript that's built in HTML, CSS and JavaScript.
Brackets 1.7 ,Brackets 是 Adobe 的开源 HTML/CSS/JavaScript 集成开发环境。国内下载很慢,上传与大家分享。
Brackets 1.6 前端开发 编辑器
brackets的扩展插件集合
Brackets Release 1.6 msi
Brackets 当前为Mac, Windows以及Linux (Debian/Ubuntu)提供最新稳定版的二进制发布, 源代码托管在GitHub上。 Adobe Brackets 1.4 发布,此版本包括一些重要的新特性:即时搜索,更好的可编辑首选项,单独启用/禁用...
brackets,前端开发利器 - Brackets 是一个免费、开源且跨平台的 HTML/CSS/JavaScript 前端 WEB 集成开发环境 (IDE工具)
内涵Brackets的主题和插件下载,大家多多支持哈哈哈哈哈...嗝
Brackets 是一个免费、开源且跨平台的 HTML/CSS/JavaScript 前端 WEB 集成开发环境 (IDE工具)。该项目由 Adobe 创建和维护...和 Sublime Text、Everedit 等通用代码编辑器不一样,Brackets 是专门针对 WEB 前端开发而生