poj 1141 Brackets Sequence 夜

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

着题的难点不在于动态规划 而在于输出

其实想想也不难 DP 后根据最优解进行递归找需要匹配的括号就可以了

代码及其注释：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<cmath>
#define LL long long

using namespace std;

const int N=105;
char s[N];
int mm[N][N];//l到r所需最少匹配
bool add[N];//是否需要匹配
int dp(int l,int r)
{
    if(l>r)
    return 0;
    if(mm[l][r]!=-1)
    return mm[l][r];
    if(l==r)//只有一个括号 必须匹配
    {
        mm[l][r]=1;
        return mm[l][r];
    }
    if(l<r)//找最优
    {
        mm[l][r]=N;
        if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))
        {
             mm[l][r]=dp(l+1,r-1);
        }
        for(int i=l;i<r;++i)
        {
            mm[l][r]=min(mm[l][r],dp(l,i)+dp(i+1,r));
        }
        return mm[l][r];
    }
    return mm[l][r];
}
void findadd(int l,int r)//找符合条件的最优向下递归 找需要匹配的括号
{
    if(l>r)
    return ;
    if(l==r)
    add[l]=true;
    if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))
    {
        if((l>r&&mm[l][r]==0)||mm[l][r]==mm[l+1][r-1])
        {
            findadd(l+1,r-1);
            return;
        }
    }
    for(int i=l;i<r;++i)
    {
        if(mm[l][i]+mm[i+1][r]==mm[l][r])
        {
            findadd(l,i);
            findadd(i+1,r);
            return ;
        }
    }

}
int main()
{
    while(gets(s))
    {
        int n=strlen(s);
        memset(mm,-1,sizeof(mm));
        memset(add,false,sizeof(add));
        dp(0,n-1);
        findadd(0,n-1);
        for(int i=0;i<n;++i)
        {
            if(add[i])
            {
                if(s[i]=='(')
                printf("%c)",s[i]);
                if(s[i]==')')
                printf("(%c",s[i]);
                if(s[i]=='[')
                printf("%c]",s[i]);
                if(s[i]==']')
                printf("[%c",s[i]);
                continue;
            }
            printf("%c",s[i]);
        }
        printf("\n");
    }
    return 0;
}