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