UVA1626 括号序列 Brackets sequence 题解

PizzaYY · 2023-03-03 18:54:19 · 题解

分析

设 s 至少需要加 p_s 个括号，转移如下：

• 如果 s 形如 (q) 或 [q]，那么 p_s = p_q；

• 如果 s 有两个及以上个字符，就把 s 分为 a,b，有 p_s=p_a+p_b。

当然，在程序中，我们需要一个二维数组 dp，dp_{i,j} 表示 s 的下标为 i\sim j 的子串 g 至少需要加的括号数。

注：用 dp_{i,i-1} 记录空串，所以对于每个 i，dp_{i,i-1} = 0；当只有一个字符，可以通过加对应的字符使其变为括号序列，所以对于每个 i，dp_{i,i} = 1。

动态规划代码如下：

void DP()
{
    memset(dp,0x3f,sizeof dp);
    for(int i = 0;i<n;i++)
        dp[i][i+1] = 0,dp[i][i] = 1;
    for(int i = n-2;i>=0;i--)
        for(int j = i+1;j<n;j++)
        {
            if(ok(s[i],s[j]))
                dp[i][j] = min(dp[i][j],dp[i+1][j-1]);
            for(int k = i;k<j;k++)//枚举分界点k 
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]); 
        }
}

现在只是求出了 dp 数组，那么怎么输出呢？

其实很简单。只需要在输出时重新检查一下哪种策略最好即可。枚举每个 dp_{i,j} 是怎么得来的。这里用递归实现。

代码如下：

void print(int i,int j)
{
    if(i>j) return;
    if(i==j)
    {
        if(s[i]=='('||s[i]==')') printf("()");
        else printf("[]");
        return;
    }
    int ans = d[i][j];
    if(ok(s[i],s[j])&&ans==d[i+1][j-1])
    {
        printf("%c",s[i]),print(i+1,j-1),printf("%c",s[j]);
        return;
    }
    for(int k = i;k<=j;k++)
        if(ans==d[i][k]+d[k+1][j])
        {
            print(i,k),print(k+1,j);
            return;
        } 
}

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int dp[N][N],n;
string s;
bool ok(int x,int y)
{
    return (s[x]=='('&&s[y]==')')||(s[x]=='['&&s[y]==']');
}
void DP()
{
    for(int i = 0;i<n;i++)
        dp[i+1][i] = 0,dp[i][i] = 1;
    for(int i = n-2;i>=0;i--)
        for(int j = i+1;j<n;j++)
        {
            dp[i][j] = n;
            if(ok(i,j))
                dp[i][j] = min(dp[i][j],dp[i+1][j-1]);
            for(int k = i;k<j;k++)//枚举分界点k 
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]); 
        }
}
void print(int i,int j)
{
    if(i>j) return;
    if(i==j)
    {
        if(s[i]=='('||s[i]==')') printf("()");
        else printf("[]");
        return;
    }
    int ans = dp[i][j];
    if(ok(i,j)&&ans==dp[i+1][j-1])
    {
        printf("%c",s[i]);
        print(i+1,j-1);
        printf("%c",s[j]);
        return;
    }
    for(int k = i;k<j;k++)
        if(ans==dp[i][k]+dp[k+1][j])
        {
            print(i,k),print(k+1,j);
            return;
        } 
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        //可能是空串 
        getline(cin,s);
        getline(cin,s);
        n = s.size();
        DP();
        print(0,n-1);
        puts("");
        if(t) puts("");//注意格式 
    }
    return 0;
}