紫书 例题 9-10 UVa 1626 (区间dp + 输出技巧)

时间:2021-02-20 02:23:25

当前区间f(i, j)分两种情况,一种是s[i]于s[j]符合要求,那么可以转移到f[i + 1][j - 1] 这样答案只会更小或者相等

第二种是直接分成两个部分, 即f[i][j] = f[i][k] + f[k + 1][j],这个时候要取min

同时要注意第一种情况未必是最优的,要从一二两种情况里面取最优值

然后输出方面,按照答案反推,如果当前状态刚好等于其中一种情况,那么就递归下去,边界是

一个字符的时候输出两个字符。

另外学会用fgets,不用gets。fgets头文件cstdio, fgets(s, MAXN, stdin);

#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std; const int MAXN = 112;
char s[MAXN];
int f[MAXN][MAXN], n; inline bool match(char a, char b)
{
return (a == '(' && b == ')') || (a == '[' && b == ']');
} void work()
{
REP(i, 0, n)
{
f[i + 1][i] = 0;
f[i][i] = 1;
}
for(int i = n - 1; i >= 0; i--)
REP(j, i + 1, n)
{
f[i][j] = n;
if(match(s[i], s[j])) f[i][j] = f[i + 1][j - 1];
REP(k, i, j)
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
}
} void print(int i, int j)
{
if(i > j) return;
if(i == j)
{
if(s[i] == '(' || s[i] == ')') printf("()");
else printf("[]");
return;
} int ans = f[i][j];
if(match(s[i], s[j]) && ans == f[i + 1][j - 1])
{
putchar(s[i]);
print(i + 1, j - 1);
putchar(s[j]);
return;
} REP(k, i, j)
if(ans == f[i][k] + f[k + 1][j])
{
print(i, k); print(k + 1, j);
return;
}
} void read(char* s)
{
fgets(s, MAXN, stdin);
} int main()
{
int T;
scanf("%d", &T);
read(s); read(s); while(T--)
{
read(s);
n = strlen(s) - 1;
work();
print(0, n -1);
puts("");
if(T) puts("");
read(s);
} return 0;
}