题目链接

其实就是括号匹配的模型。。用栈即可。。被我写挂好几发。。该死该死。。。

/* ***********************************************
Author :111qqz
Created Time :2016年08月07日 星期日 17时34分13秒
File Name :code/whust2016/#1/HH.cpp
************************************************ */

1#include <cstdio>
2#include <cstring>
3#include <iostream>

 1 …

poj 1141题目链接

题意：给出一个括号序列，要求添加最少的括号，使得这个序列变成合法的括号匹配，输出最后的序列。

思路：区间dp。。。有了那么一点思路。。。我们可以用dp[i][j]表示区间[i,j]的序列最少需要添加几个符号使得匹配。。转移的话。。。和之前差不多。。dp[i][j] = dp[i+1][j-1] (s[i]与s[j])匹配。。。不匹配的话也是找中间某个点。。。初始化的话。。要变成最大值。。。比较没思路的是输出括号序列这部分。。。