代码如下～
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 110;
const int INF = 65536;

char str[N];
int f[N][N], act[N][N];
bool finish[N][N];

void Outchar(char c)
{
    switch(c)
    {
        case '(': printf(")"); break;
        case ')': printf("("); break;
        case '[': printf("]"); break;
        case ']': printf("["); break;
    }
}

bool Yes(char c1, char c2)
{
    if(c1=='(' && c2==')')  return true;
    if(c1=='[' && c2==']')  return true;
    return false;
}

void Dp(int l, int r)
{
    int i;
    if(finish[l][r])  return;
    if(l == r)
    {
        f[l][r] = 1;
        return;
    }
    if(l > r)
    {
        f[l][r] = 0;
        return;
    }
    f[l][r] = INF;
    if(Yes(str[l], str[r]))
    {
        Dp(l+1, r-1);
        if(f[l+1][r-1] < f[l][r])
        {
            f[l][r] = f[l+1][r-1];
            act[l][r] = 0;
        }
    }
    for(i = l; i < r; i++)
    {
        Dp(l, i);
        Dp(i+1, r);
        if(f[l][i]+f[i+1][r] < f[l][r])
        {
            f[l][r] = f[l][i]+f[i+1][r];
            act[l][r] = i;
        }
    }
    finish[l][r] = true;
}

void Print(int l, int r)
{
    if(l == r)
    {
        switch(str[l])
        {
            case '(': printf("()"); break;
            case ')': printf("()"); break;
            case '[': printf("[]"); break;
            case ']': printf("[]"); break;
        }
        return;
    }
    if(l > r)  return;
    if(act[l][r] == 0)
    {
        printf("%c", str[l]);
        Print(l+1, r-1);
        printf("%c", str[r]);
    }
    else
    {
        Print(l, act[l][r]);
        Print(act[l][r]+1, r);
    }
}

int main()
{
    int len;
    char s[N];
    scanf("%s", s);
    len = strlen(s);
    if(len == 0)
    {
        printf("\n");
        return 0;
    }
    for(int i=0; i < len; i++)  str[i+1] = s[i];
    memset(act, -1, sizeof(act));
    memset(finish, false, sizeof(finish));
    Dp(1, len);
    Print(1, len);
    printf("\n");
    return 0;
}

• Re:见鬼了，C++WA， G++AC～ (2366) 834208094 2012-08-09 20:36:51