Problem UVA1626-Brackets sequence

Time Limit: 4500 mSec

Problem Description

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs. The input file contains at most 100 brackets (characters ‘(’, ‘)’, ‘[’ and ‘]’) that are situated on a single line without any other characters among them.

 Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.
 

 Sample Input

1
([(]
 

Sample Output

()[()]

题解:这个题挺好的,区间dp,可以写成记忆化搜索,容易忽略的地方是如果区间两边的括号匹配,那么可以用中间的部分转移,然后就是普通的分成左区间和右区间进行转移,这个题比较有价值的地方在于打印解的过程,应该学习一下,就是根据结果,逆推回去,这个方便在不用中间记录转移路径,代价就是时间上会有额外的开销,不过一般不至于因此就TLE,因为解一般很少。输入输出有坑,需要用fgets,并且注意fgets会把最后的'\n'读进来,因此真实串的长度需要-1.

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn =  + ;

 int iCase, dp[maxn][maxn];
char bra[maxn];
bool vis[maxn][maxn]; bool match(char a, char b) {
if ((a == '(' && b == ')') || (a == '[' && b == ']')) return true;
return false;
} int DP(int l, int r) {
if (dp[l][r] >= ) return dp[l][r];
if (l == r) return dp[l][r] = ;
if (l > r) return dp[l][r] = ; int &ans = dp[l][r];
ans = r - l + ;
if (match(bra[l], bra[r])) {
ans = min(ans, DP(l + , r - ));
}
for (int k = l; k < r; k++) {
ans = min(ans, DP(l, k) + DP(k + , r));
}
return ans;
} void ans_print(int l, int r) {
if (l > r) return;
if (l == r) {
if (bra[l] == '(' || bra[l] == ')') {
printf("()");
}
else {
printf("[]");
}
return;
} int &ans = dp[l][r];
if (match(bra[l], bra[r]) && ans == dp[l + ][r - ]) {
printf("%c", bra[l]);
ans_print(l + , r - );
printf("%c", bra[r]);
return;
}
else {
for (int k = l; k < r; k++) {
if (ans == dp[l][k] + dp[k + ][r]) {
ans_print(l, k);
ans_print(k + , r);
return;
}
}
}
} int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d\n", &iCase);
while (iCase--) {
fgets(bra, maxn, stdin);
memset(dp, -, sizeof(dp));
int len = strlen(bra);
int ans = DP(, len - );
ans_print(, len - );
printf("\n");
if (iCase) printf("\n");
fgets(bra, maxn, stdin);
}
return ;
}

最新文章

  1. weblogic安全漫谈
  2. fastq-dump 报错 解决方案
  3. ABAP 通过视图取数到内表函数
  4. 通过button返回一个action,跳转到一个view
  5. Http协议中 常用的参数应用
  6. 细聊分布式ID生成方法
  7. 纯CSS最小响应网格布局
  8. 【First Missing Positive】cpp
  9. 用UNetbootin来安装USB LINUX,好像比ULTRA ISO省事
  10. 伺服驱动器UVW电机电源线相序错误
  11. 蓝桥杯比赛javaB组练习《饮料换购》
  12. UWP上可用的GB2312编码
  13. 【前端单元测试入门05】react的单元测试之jest
  14. Ubuntu16.04开机引导缺失Win10
  15. java设计模式--观察者模式(Observer)
  16. 一.从零认识XAML
  17. Laravel5.5学习笔记
  18. LeetCode 147. Insertion Sort List 链表插入排序 C++/Java
  19. 在SecureCRT中做make menuconfig乱码
  20. #JS 获取屏幕分辨率、网页可见区域等

热门文章

  1. BZOJ2144: 跳跳棋
  2. 深入浅出 - Android系统移植与平台开发(四)- Android启动流程
  3. js数组基础知识链接
  4. Black 全面分析
  5. MVVM架构的一次实践,重写iOS头条客户端
  6. jquery 上下滑动效果
  7. Python系列之多线程、多进程
  8. javaEmail发邮件是问号乱码,已解决
  9. atitit 读书与获取知识资料的attilax的总结.docx
  10. 【软件工程Ⅱ】作业二 |分布式版本控制系统Git的安装与使用
  11. CAP与Base理论
  12. 爬虫实战(二) 51job移动端数据采集
  13. CF1111E Tree 树链剖分,DP
  14. 关于Android原生Email的自己的一些认识
  15. AndroidStudio怎样导入library项目开源库
  16. zabbix连不上数据库
  17. 【转】linux下,如何把整个文件夹上传到服务器(另一台linux)
  18. harbor 管理Helm Chart包
  19. 中兴G718C开发者模式开启
  20. Linux命令应用大词典-第14章 显示登录用户