poj 1141 Brackets Sequence (区间dp,括号匹配，记录路径)

题意：给出一个括号序列，要求添加最少的括号，使得这个序列变成合法的括号匹配，输出最后的序列。

思路：区间dp。。。有了那么一点思路。。。我们可以用dp[i][j]表示区间[i,j]的序列最少需要添加几个符号使得匹配。。转移的话。。。和之前差不多。。dp[i][j] = dp[i+1][j-1] (s[i]与s[j])匹配。。。不匹配的话也是找中间某个点。。。初始化的话。。要变成最大值。。。比较没思路的是输出括号序列这部分。。。

参考了这篇题解：参考题解

记录路径的思路是。。。记录转移的点。。。

cut[i][j]表示的是区间[i,j]的最优值是由点cut[i][j]这里划分得到的。。。

cut[i][j]为-1表示区间[i,j]的最优值不是从中间分成两部分得到。。。

打印路径的时候。。。如果[i,j]的长度小于等于0.。直接return.

如果长度为1.。。直接输出。。。

如果长度大于1.。。。要分这段区间是否中间有划分两种情况。。具体见代码。。。

代码实现

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年07月25日 星期一 15时55分47秒
  4File Name :code/poj/1141.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33char s[105];
 34int dp[105][105]; //dp[i][j]表示区间[i,j]最少需要添加多少字符达到匹配。
 35int cut[105][105] ; //记录一段区间是在哪里断开最优，是为了记录路径，打印括号
 36bool check(char a,char b)
 37{
 38    if (a=='['&&b==']') return true;
 39    if (a=='('&&b==')') return true;
 40    return false;
 41}
 42
 43void print(int i ,int j)
 44{
 45    if (i>j) return ;
 46    if (i==j)
 47    {
 48	if (s[i]=='('||s[i]==')') printf("()");
 49	if (s[i]=='['||s[i]==']') printf("[]");
 50	return ;
 51    }
 52    if (cut[i][j]==-1)
 53    {
 54	printf("%c",s[i]);
 55	print(i+1,j-1);
 56	printf("%c",s[j]);
 57    }
 58    else
 59    {
 60	print(i,cut[i][j]);
 61	print(cut[i][j]+1,j);
 62    }
 63}
 64int main()
 65{
 66	#ifndef  ONLINE_JUDGE
 67	freopen("code/in.txt","r",stdin);
 68  #endif
 69
 70	scanf("%s",s);
 71
 72	    int len = strlen(s);
 73	    ms(dp,0x3f);
 74	    ms(cut,-1);
 75	    for ( int i = 0 ; i <=len ; i++) dp[i][i] = 1;
 76
 77	    for ( int l = 1 ; l  < len ; l++)
 78	    {
 79		for ( int i = 0 , j = l ; j < len ; i++,j++)
 80		{
 81		    dp[i][j] = inf;
 82		    if (check(s[i],s[j]))
 83		    {
 84			dp[i][j] = dp[i+1][j-1]; //当前匹配的话，就不需要增加字符
 85			cut[i][j] = -1;
 86		    }
 87
 88		    for ( int k = i ; k < j ; k++)
 89			if (dp[i][j]>dp[i][k]+dp[k+1][j])
 90			{
 91			    dp[i][j] = dp[i][k] + dp[k+1][j];
 92			    cut[i][j] = k;
 93			}
 94		}
 95	    }
 96
 97	    print(0,len-1);
 98	    printf("\n");
 99
100
101  #ifndef ONLINE_JUDGE
102  fclose(stdin);
103  #endif
104    return 0;
105}

相关文章