记忆化搜索(DP+DFS) URAL 1183 Brackets Sequence

题目传送门

 /*
记忆化搜索(DP+DFS):dp[i][j] 表示第i到第j个字符,最少要加多少个括号
dp[x][x] = 1 一定要加一个括号;dp[x][y] = 0, x > y;
当s[x] 与 s[y] 匹配,则搜索 (x+1, y-1); 否则在x~y-1枚举找到相匹配的括号,更新最小值
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cstring>
using namespace std; const int MAXN = 1e2 + ;
const int INF = 0x3f3f3f3f;
int dp[MAXN][MAXN];
int pos[MAXN][MAXN];
char s[MAXN]; void DFS(int x, int y)
{
if (dp[x][y] != -) return ;
if (x > y) {dp[x][y] = ; return ;}
if (x == y) {dp[x][y] = ; return ;} dp[x][y] = INF;
if ((s[x]=='(' && s[y]==')') || (s[x]=='[' && s[y]==']'))
{
pos[x][y] = -;
DFS (x+, y-);
dp[x][y] = dp[x+][y-];
}
for (int i=x; i<y; ++i)
{
DFS (x, i); DFS (i+, y);
int cur = dp[x][i] + dp[i+][y];
if (cur < dp[x][y])
{
dp[x][y] = cur; pos[x][y] = i;
}
}
} void print(int x, int y)
{
if (x > y) return ;
if (x == y)
{
if (s[x] == '(' || s[y] == ')') printf ("()");
else printf ("[]");
return ;
}
if (pos[x][y] == -)
{
printf ("%c", s[x]);
print (x+, y-);
printf ("%c", s[y]);
}
else
{
print (x, pos[x][y]); print (pos[x][y]+, y);
}
} int main(void) //URAL 1183 Brackets Sequence
{
//freopen ("O.in", "r", stdin); while (scanf ("%s", s+) == )
{
int len = strlen (s+);
memset (dp, -, sizeof (dp));
memset (pos, , sizeof (pos)); DFS (, len);
print (, len); puts ("");
} return ;
}
上一篇:hdu 1208 记忆化搜索


下一篇:labview图形和图表的类型