学步园

ZOJ 1463 POJ1141 Brackets Sequence (区间DP) #by Plato

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=463

题意： 给一个括号序列，求 为使序列合法化所需要添加的最少括号书。要求输出合法化后的序列。

Idea： 比较明显的DP了，

f[i][j] 代表从 第i个元素到第j个元素所需要添加的最小括号数，

以i-j的距离扩大开始DP，

4种状态转移的方式：

                  条件           结果           路径

a[ i] – ‘)’   a[i]为左括号       f[i+1][j]+1  -1

‘(‘ – a[j]               a[j]为右括号       f[i][j-1] +1          -2

a[i] – a[j]   a[i]与a[j]匹配    f[i+1][j-1] -3

a[i] – a[m],a[m+1]-a[j]                  f[i][m]+ f[m+1][j]       m

有关路径记录，有多种方案，这里采用的是 直接记录 每一状态转移过来的方法，然后递归还原插入到相应的位置，最后输出。

注意：此题有个巨坑，最后一组测试数据是空行（没错，输入的字符串<=100）。ZOJ是把多个数据集合在一组里，读入字符串不能用scanf，要用gets。POJ是单组数据测，就随意了。

#include <cstdio>
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <vector>
#define OP(s) cout<<#s<<"="<<s<<" ";
#define PP(s) cout<<#s<<"="<<s<<endl;
using namespace std;

char a[110];
int path[110][110];
vector<char> pre[110],next[110];

inline char kh(char s)
{
    switch (s)
    {
    case '(' :
        return ')';
    case ')' :
        return '(';
    case '[' :
        return ']';
    case ']' :
        return '[';
    }
}

void find(int l,int r)
{
    if (l > r) return ;
    int m = path[l][r];
    if (m == -1)
    {
        next[r].push_back(kh(a[l]));
        find(l+1,r);
    }
    if (m == -2)
    {
        pre[l].push_back(kh(a[r]));
        find(l,r-1);
    }
    if (m == -3) find(l+1,r-1);
    if (m > 0) find(l,m),find(m+1,r);

}

int main()
{
    freopen("test.txt","r",stdin);
    int T;
    scanf("%d",&T);
    getchar();
    for (int cas = 0; cas < T; cas++)
    {
        if (cas) cout<<endl;
        //scanf("%s",&a[1]);
        getchar();
        gets(a);
        int len = strlen(a);
        for (int i = len;i >= 1;i--) a[i] = a[i-1];
        a[0] = '#';
        a[len+1] = 0;

        static int f[110][110];
        memset(path,0,sizeof(path));
        memset(f,0,sizeof(f));
        for (int i = 1; i <= len; i++)
        {
            f[i][i] = 1;
            if (a[i] == '[' || a[i] == '(') path[i][i] = -1;
            if (a[i] == ']' || a[i] == ')') path[i][i] = -2;
        }

        for (int k = 1; k <= len-1; k++)
        {
            for (int i = 1; i <= len; i++)
            {
                int j = i+k;
                if (j > len) break;
                f[i][j] = 1<<30;
                if ((a[i] == '(' && a[j] == ')' || a[i] == '[' && a[j] == ']') && f[i+1][j-1] < f[i][j]) f[i][j] = f[i+1][j-1],path[i][j] = -3;
                for (int m = i; m < j; m++)
                    if (f[i][m]+f[m+1][j] < f[i][j]) f[i][j] = f[i][m] + f[m+1][j],path[i][j] = m;
                if (a[i] == '(' || a[i] == '[') if (f[i+1][j] + 1 < f[i][j]) f[i][j] = f[i+1][j] +1,path[i][j] = -1;
                if (a[j] == ')' || a[j] == ']') if (f[i][j-1] + 1 < f[i][j]) f[i][j] = f[i][j-1]+1,path[i][j] = -2;
            }
        }

        for (int i = 0; i <= 109; i++)
            pre[i].clear(),next[i].clear();

        find(1,len);

        for (int i = 1; i <= len; i++)
        {
            int size = next[i-1].size();
            for (int j = size - 1; j >= 0; j--) printf("%c",next[i-1][j]);
            size = pre[i].size();
            for (int j = 0; j < size; j++) printf("%c",pre[i][j]);
            printf("%c",a[i]);
        }
        int size = next[len].size();
        for (int j = size-1; j >= 0; j--) printf("%c",next[len][j]);
        cout<<endl;
    }


    return 0;
}