本文主要是介绍【UVA】1626-Brackets sequence（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一道算是比较难理解的动规。
状态转移分2个：
（用d[i][j]表示在i~j内最少需要添加几个括号，保持平衡）
1.如果s[i]和s[j]是一对括号，那么d[i][j] = d[i + 1][j - 1]
2.否则的话 d[i][j] = min(d[i][k],[k + 1][j]);
边界是d[i + 1][i] = 0; d[i][i] = 1;
| 13993644 | 1626 | Brackets sequence | Accepted | C++ | 1.109 | 2014-08-05 10:18:17 |
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<ctime>
#include<cmath>
#include<string>
#include<iomanip>
#include<climits>
#include<cctype>
#include<deque>
#include<list>
#include<sstream>
#include<vector>
#include<cstdlib>
using namespace std;
#define _PI acos(-1.0)
#define INF (1 << 20)
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pill;
/*======================================*/
#define MAXD 1000 + 10
char str[MAXD];
int dp[MAXD][MAXD];/*串i,j需要增加几个括号*/
void init(){for(int i = 0 ; i < strlen(str) ; i++){dp[i + 1][i] = 0;dp[i][i] = 1;}return ;
}
bool is_ok(int i,int j){if(str[i] == '(' && str[j] == ')')return true;else if(str[i] == '[' && str[j] == ']')return true;elsereturn false;
}
void print(int i,int j){if(i > j)return ;if(i == j){if(str[i] == '(' || str[i] == ')')printf("()");elseprintf("[]");}int ans = dp[i][j];if(is_ok(i,j) && ans == dp[i + 1][j - 1]){printf("%c",str[i]);print(i + 1, j - 1);printf("%c",str[j]);return ;}for(int k = i ; k < j ; k++){if(ans == dp[i][k] + dp[k + 1][j]){print(i,k);print(k + 1,j);return ;}}
}
void DP(){init();int n = strlen(str);for(int i = n - 2 ; i >= 0 ; i --){for(int j = i + 1 ; j < n ; j++){dp[i][j] = n;if(is_ok(i,j)){dp[i][j] = min(dp[i][j],dp[i + 1][j - 1]);}for(int k = i ; k < j ; k++)dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j]);}}if(!dp[0][n - 1])printf("%s",str);elseprint(0,n - 1);return ;
}
int main(){int T;scanf("%d%*c",&T);while(T--){if(!strlen(str));elseDP();printf("\n");if(T)printf("\n");}return 0;
}
这篇关于【UVA】1626-Brackets sequence（动态规划）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
