UVa1626 - Brackets sequence（区间dp）

题目链接

简介：
匹配括号
提示：空串是合法序列

分析：
比较基础的题：
f[i][j]表示(i~j)括号匹配过之后需要添加的最少括号数

• 如果s[i]和s[j]能够匹配的上，那么f[i][j]=min(f[i][j]，f[i-1][j+1])

• 枚举中点k，f[i][j]=min{f[i][k]+f[k+1][j]}

注意：

无论第一种转移方式合不合法，我们都要尝试第二种
（因为有“[ ][ ]“这样的状态）

我们之所以先计算最少的括号添加数，就是为了方案输出
方案输出的时候，我们实际就是按照f值再推回去

void print(int i,int j)
{
    if (i>j) return;
    if (i==j)
    {
        if (s[i]=='('||s[j]==')') printf("()");
        else printf("[]");
        return;
    }
    int ans=f[i][j];
    if (match(i,j)&&ans==f[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==f[i][k]+f[k+1][j]) {print(i,k); print(k+1,j);return;}
}

tip

这道题的坑点不是一般的难克服。。。
因为有大量的空串和回车输入，
（输入n后有一个空行，每两个输入数据中间又有空行）
我们不能再用无脑的scanf了，我选择的是gets

gets
从标准输入设备读字符串函数，其可以无限读取，不会判断上限，以回车结束读取

在输出的时候少了一个return，就T了几次

之后又是WA：
注意解之间空行的输出（干脆固定下来）：

int cnt=0;
if (cnt++) printf("\n");

//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

char s[110];
int f[110][110];

int match(int x,int y)
{
    if (s[x]=='('&&s[y]==')') return 1;
    if (s[x]=='['&&s[y]==']') return 1;
    return 0;
}

void doit()
{
    int i,j,k;
    int len=strlen(s);
    memset(f,0x33,sizeof(f));
    for (i=0;i<len;i++) f[i][i]=1,f[i+1][i]=0;
    for (i=len-2;i>=0;i--)
        for (j=i+1;j<len;j++)
        {
            if (match(i,j)) f[i][j]=min(f[i][j],f[i+1][j-1]);
            for (k=i;k<j;k++)
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
        }
}

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

int main()
{
    int T,cnt=0;
    scanf("%d",&T);
    getchar();
    while (T--)
    {
        gets(s);
        gets(s);
        int n=(int)strlen(s);
        if (n==0) {if (cnt++) printf("\n");printf("\n");continue;}

        doit();

        if (cnt++) printf("\n");
        print(0,strlen(s)-1);
        printf("\n");   
    }
    return 0;
}