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

poj 1141题目链接

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

思路:区间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.。。。要分这段区间是否中间有划分两种情况。。具体见代码。。。

/* ***********************************************
Author :111qqz
Created Time :2016年07月25日 星期一 15时55分47秒
File Name :code/poj/1141.cpp
************************************************ */
 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6char s[105];
 7int dp[105][105]; //dp[i][j]表示区间[i,j]最少需要添加多少字符达到匹配。
 8int cut[105][105] ; //记录一段区间是在哪里断开最优,是为了记录路径,打印括号
 9bool check(char a,char b)
10{
11    if (a=='['&&b==']') return true;
12    if (a=='('&&b==')') return true;
13    return false;
14}
 1void print(int i ,int j)
 2{
 3    if (i>j) return ;
 4    if (i==j)
 5    {
 6	if (s[i]=='('||s[i]==')') printf("()");
 7	if (s[i]=='['||s[i]==']') printf("[]");
 8	return ;
 9    }
10    if (cut[i][j]==-1)
11    {
12	printf("%c",s[i]);
13	print(i+1,j-1);
14	printf("%c",s[j]);
15    }
16    else
17    {
18	print(i,cut[i][j]);
19	print(cut[i][j]+1,j);
20    }
21}
22int main()
23{
24	#ifndef  ONLINE_JUDGE 
25	freopen("code/in.txt","r",stdin);
26  #endif
	scanf("%s",s);
1	    int len = strlen(s);
2	    ms(dp,0x3f);
3	    ms(cut,-1);
4	    for ( int i = 0 ; i <=len ; i++) dp[i][i] = 1;
 1	    for ( int l = 1 ; l  < len ; l++)
 2	    {
 3		for ( int i = 0 , j = l ; j < len ; i++,j++)
 4		{
 5		    dp[i][j] = inf;
 6		    if (check(s[i],s[j]))
 7		    {
 8			dp[i][j] = dp[i+1][j-1]; //当前匹配的话,就不需要增加字符
 9			cut[i][j] = -1; 
10		    }
1		    for ( int k = i ; k < j ; k++)
2			if (dp[i][j]>dp[i][k]+dp[k+1][j])
3			{
4			    dp[i][j] = dp[i][k] + dp[k+1][j];
5			    cut[i][j] = k;
6			}
7		}
8	    }
	    print(0,len-1);
	    printf("\n");
1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}