本文主要是介绍ural Brackets Sequence (dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.timus.ru/problem.aspx?space=1&num=1183
很经典的问题吧，看的黑书上的讲解。
设dp[i][j]表示i到j括号合法需要的最少括号数。
共有四种情况：
s[i]s[j]配对，dp[i][j] = min( dp[i][j] , dp[i-1][j+1] )；
s[i] = '('或'[' dp[i][j] = min( dp[i][j] , dp[i+1][j]+1 )；
s[j] = ')'或']' dp[i][j] = min( dp[i][j] , dp[i][j-1]+1 )；
dp[i][j] = min( dp[i][k]+dp[k+1][j] )（i <= k < j-1）
同时拿一个数组记录到达这种状态是哪种方式，然后dfs输出。
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 50010;int dp[110][110];
int way[110][110];
char s[110];
int len;void dfs(int l, int r)
{if(l > r) //少写一句，1wareturn;if(l == r){if(s[l] == '(' || s[l] == ')')printf("()");else if(s[l] == ']' || s[l] == '[')printf("[]");return;}if(way[l][r] == 0){printf("%c",s[l]);dfs(l+1,r-1);printf("%c",s[r]);return;}else if(way[l][r] == -1){printf("%c",s[l]);dfs(l+1,r);printf("%c",s[l]=='('?')':']');return;}else if(way[l][r] == -2){printf("%c",s[r]==')'?'(':'[');dfs(l,r-1);printf("%c",s[r]);return;}else{dfs(l,way[l][r]);dfs(way[l][r]+1,r);return;}}void solve()
{for(int i = 1; i <= len; i++){dp[i][i] = 1;dp[i][i-1] = 0;}for(int p = 1; p <= len-1; p++){for(int i = 1; i <= len-p; i++){int j = i+p;dp[i][j] = INF;if( (s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']') ){if(dp[i][j] > dp[i+1][j-1]){dp[i][j] = dp[i+1][j-1];way[i][j] = 0;}}if(s[i] == '(' || s[i] == '['){if(dp[i][j] > dp[i+1][j]+1){dp[i][j] = dp[i+1][j]+1;way[i][j] = -1;}}if(s[j] == ')' || s[j] == ']'){if(dp[i][j] > dp[i][j-1]+1){dp[i][j] = dp[i][j-1]+1;way[i][j] = -2;}}for(int k = i; k <= j-1; k++){if(dp[i][j] > dp[i][k]+dp[k+1][j]){dp[i][j] = dp[i][k] + dp[k+1][j];way[i][j] = k;}}}}
}int main()
{while(~scanf("%s",s+1)){len = strlen(s+1);solve();dfs(1,len);printf("\n");}return 0;
}
这篇关于ural Brackets Sequence (dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
