区間dpモデルのかっこマッチング印刷経路poj(1141)

タイトルリンク:Brackets Sequenceタイトル説明:'(')''[''']'からなる一連の列を与え、最小カッコを追加した後にカッコを一致させる列を出力させます.解析:区間dpの古典的なモデルカッコマッチングです.説明:http://blog.csdn.net/y990041769/article/details/24194605 難点は、マッチしたかっこを出すことです.
まず,dp[i][j]が列中のi番目からj番目の括弧の最大マッチング数として定義されていることを知る.
では、任意のiからjがどこから点数を挿入するかを知っていれば、マッチングに括弧を最小限に抑えることができます.では、pos【i】【j】は、iからjがどこから離れているかを定義し、マッチングに括弧を最小限に抑えることができ、iとjがマッチングすればpos【i】【j】=-1にすることができる.
我々が以前にdp[i][j]を更新したとき,中間点kがif(dp[i][k]+dp[k+1][j]>=dp[i][j])になるようにすれば,kから分離して追加した括弧を最小限に抑えることができることを見出した.
ただし、「((()」のようにすべてが一致しないことを考慮し、どのように処理するかを考慮すると、結果を再帰的に出力することができることに注意してください.
この問題は私が何度も穴をあけて、Telを始めたばかりで、すべて一致していないことに気づいて処理できないことを発見して、直した後にwaになりました.
コード:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int  N = 120;
int dp[N][N],pos[N][N];   ///i j               
char s[N];
void show(int i,int j)
{
    if(i>j)  return;
    if(i==j)
    {
        if(s[i]=='('||s[i]==')') cout<<"()";
        else      cout<<"[]";
    }
    else
    {
        if(pos[i][j]==-1)
        {
            cout<<s[i];
            show(i+1,j-1);
            cout<<s[j];
        }
        else
        {
            show(i,pos[i][j]);
            show(pos[i][j]+1,j);
        }
    }
}
int main()
{
    while(gets(s))
    {
        memset(dp,0,sizeof(dp));
        int len=strlen(s);
        for(int i=1; i<len; i++)
        {
            for(int j=0,k=i; k<len; j++,k++)
            {
                if(s[j]=='('&&s[k]==')' || s[j]=='['&&s[k]==']')
                {
                    dp[j][k]=dp[j+1][k-1]+2;
                    pos[j][k]=-1;
                }
                for(int f=j; f<k; f++)
                {
                    if(dp[j][f]+dp[f+1][k]>=dp[j][k])  ///                 
                    {
                        dp[j][k]=dp[j][f]+dp[f+1][k];
                        pos[j][k]=f;
                    }
                }
            }
        }
        //cout<<s.size()-dp[0][s.size()-1]<<endl;
        show(0,len-1);cout<<endl;
    }
    return 0;
}