http://poj.org/problem?id=1141
DP, 记录路径。
# include <stdio.h>
# include <string.h>
# define N 205
# define INF 1000000000
# define Mid (1 << 10)
# define Lft (1 << 9 )
# define Rgt (1 << 8 )
char buf[N];
int f[N][N], p[N][N];
int dp(int x, int y)
{
int & ans = f[x][y];
if (ans != -1) return ans;
if (x > y) return ans = 0;
ans = INF;
if ( (buf[x]=='('&&buf[y]==')') ||
(buf[x]=='['&&buf[y]==']') )
{
if (ans > dp(x+1, y-1))
{
p[x][y] = Mid;
ans = f[x+1][y-1];
}
}
if ( buf[x]=='(' || buf[x]=='[' )
{
if (ans > dp(x+1, y)+1)
{
p[x][y] = Rgt;
ans = f[x+1][y] + 1;
}
}
if ( buf[y]==')' || buf[y]==']' )
{
if (ans > dp(x, y-1)+1)
{
p[x][y] = Lft;
ans = f[x][y-1] + 1;
}
}
for (int i = x; i < y; ++i)
{
if (ans > dp(x, i)+dp(i+1, y))
{
p[x][y] = i;
ans = f[x][i] + f[i+1][y];
}
}
return ans;
}
void print(int s, int t)
{
switch(p[s][t])
{
case Mid:
{
putchar(buf[s]), print(s+1, t-1), putchar(buf[t]);
break;
}
case Lft:
{
if (buf[t] == ')')
putchar('('), print(s, t-1), putchar(')');
else
putchar('['), print(s, t-1), putchar(']');
break;
}
case Rgt:
{
if (buf[s] == '(')
putchar('('), print(s+1, t), putchar(')');
else
putchar('['), print(s+1, t), putchar(']');
break;
}
case 0:
{
for (int i = s; i <= t; ++i)
putchar(buf[i]);
break;
}
default:
{
print(s, p[s][t]), print(p[s][t]+1, t);
break;
}
}
}
int main()
{
int n;
buf[0] = 0, scanf("%s", buf+1);
memset(f, -1, sizeof(f));
memset(p, 0, sizeof(p));
n = strlen(buf+1);
dp(1, n), print(1, n), putchar('\n');
return 0;
}
posted on 2012-10-11 13:57
yajunw 阅读(232)
评论(0) 编辑 收藏 引用