poj1141 Brackets Sequence（区间dp）

poj1141

分析

第一次做区间dp，讲解的话这微博主讲的很清楚了。http://www.cnblogs.com/neulike/archive/2011/02/12/1952600.html

题目

http://poj.org/problem?id=1141

代码

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>

using namespace std;

const int inf=0x3f3f3f3f;

string s;
int d[110][110],value[110][110],len;

void fun()
{
    for(int i=0; i<len; i++) d[i][i]=1;
    for(int tem=1; tem<len; tem++)
        for(int i=0; i<len-tem; i++)
        {
            int j=tem+i;
            d[i][j]=inf;
            if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']'))
            {
                d[i][j]=d[i+1][j-1];
                value[i][j]=-1;
            }
            for(int k=i; k<j; k++)
                if(d[i][j]>d[i][k]+d[k+1][j])
                {
                    d[i][j]=d[i][k]+d[k+1][j];
                    value[i][j]=k;
                }
        }
    return;
}

void print(int i,int j)
{
    if(i>j) return;
    else if(i==j)
    {
        if(s[i]==')'||s[i]=='(') printf("()");
        if(s[i]==']'||s[i]=='[') printf("[]");
    }
    else if(value[i][j]==-1)
    {
        printf("%c",s[i]);
        print(i+1,j-1);
        printf("%c",s[j]);
    }
    else
    {
        print(i,value[i][j]);
        print(value[i][j]+1,j);
    }
    return;
}

int main()
{

    while(getline(cin,s))
    {
        memset(d,0,sizeof(d));
        len=(int)s.length();
        fun();
        print(0,len-1);
        printf("\n");
    }

}