poj 1141 （区间dp记录路径问题）

忘是亡心i 2022-08-18 11:56 155阅读 0赞

题意：括号匹配问题。问需要插入多少个括号是的所有的括号都正好可以匹配。输出其中长度最短的一个。

分析：dp\[i\]\[j\] 表示的是在区间(i,j)之间添加的最少的括号数，c\[i\]\[j\] 记录断开的位置，没有断开的话记为-1。

dp\[i\]\[i\] = 1;

当s\[i\]=='(' && s\[j\]==')' 或者 s\[i\]=='\[' && s\[j\]=='\]'时，d\[i\]\[j\]=d\[i+1\]\[j-1\]

否则d\[i\]\[j\]=min\{d\[i\]\[k\]+d\[k+1\]\[j\]\} i<=k<j ，  c\[i\]\[j\]记录断开的位置k

采用递推方式计算d\[i\]\[j\]

输出结果时采用递归方式输出print(0, len-1)

输出函数定义为print(int i, int j)，表示输出从下标i到下标j的合法序列

当i>j时，直接返回，不需要输出

当i==j时，d\[i\]\[j\]为1，至少要加一个括号，如果s\[i\]为'(' 或者')'，输出"()"，否则输出"\[\]"

当i>j时，如果c\[i\]\[j\]>=0，说明从i到j断开了，则递归调用print(i, c\[i\]\[j\]);和print(c\[i\]\[j\]+1, j);

如果c\[i\]\[j\]<0，说明没有断开，如果s\[i\]=='(' 则输出'('、 print(i+1, j-1); 和")"

否则输出"\[" print(i+1, j-1);和"\]"

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int const maxn = 300;
    int dp[maxn][maxn];   //dp[i][j] 表示的是在区间(i,j)之间添加的最少的括号数
    int c[maxn][maxn];    //c[i][j] 记录断开的位置
    char str[maxn];
    
    //采用递归输出
    void print(int st,int en)
    {
        if(st>en)return ;
        if(st==en)
        {
            if(str[st]=='('||str[st]==')')
                printf("()");
            else printf("[]");
        }
        else if(c[st][en]==-1)
        {
            printf("%c",str[st]);
            print(st+1,en-1);
            printf("%c",str[en]);
        }
        else
        {
            print(st,c[st][en]);
            print(c[st][en]+1,en);
        }
    }
    
    int main()
    {
        scanf("%s",str);
        int n = strlen(str);
        memset(c,0,sizeof(c));
        for(int i = 0 ; i < n ; i++)
        {
            dp[i][i] = 1 ;
    //            if((str[i]=='('&&str[i+1]==')')||(str[i]=='['&&str[i+1]==']'))
    //                dp[i][i+1] = 0;
    //            else dp[i][i+1] = 2;
        }
        for(int k = 1 ; k < n ; k++)
        {
            for(int i = 0 , j = k ; j < n ; i++ , j++)
            {
                if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']'))
                {
                    dp[i][j] = dp[i+1][j-1] ;
                    c[i][j] = -1 ;
                }
                else dp[i][j] = 0x3f3f3f3f;
                for(int x = i ; x < j ; x++)
                {
                    if(dp[i][j]>dp[i][x]+dp[x+1][j])
                    {
                        dp[i][j] = dp[i][x]+dp[x+1][j] ;
                        c[i][j] = x ;
                    }
                }
            }
        }
        print(0,n-1);
        printf("\n");
        return 0;
    }
    /*
    Auther:LIUYAN
    2015.12.16
    ([(]
    */