Felicia
[动态规划]pku1141
int f[i][j]表示第i个字符到第j个字符需要添加的最少括号数。string ans[i][j] 表示第i个字符到第j个字符按照最优方案添加括号后的串。状态转移：1.f[i][j]由f[i + 1][j - 1]转移来（通过两端添括号() / [] ）。2.f[i][j]由f[i][k] + f[k + 1][j]转移来（通过串合并）。答案是ans[0][len - 1]。

/*************************************************************************
Author: WHU_GCC
Created Time: 2007-8-27 9:54:57
File Name: pku1141.cpp
Description: 
************************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
const int maxint = 0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) {for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

const int maxn = 110;

char s[maxn];
int len;

int f[maxn][maxn];
string ans[maxn][maxn];

void dp()
{
    memset(f, 0, sizeof(f));
    for (int i = 0; i < len; i++)
        for (int j = i; j < len; j++)
        {
            f[i][j] = maxint;
            ans[i][j] = "";
        }
    for (int i = len - 1; i >= 0; i--)
        for (int j = i; j < len; j++)
            if (i == j)
            {
                f[i][j] = 1;
                if (s[i] == '(') ans[i][j] = "()";
                if (s[i] == ')') ans[i][j] = "()";
                if (s[i] == '[') ans[i][j] = "[]";
                if (s[i] == ']') ans[i][j] = "[]";
            }
            else
            {
                if (j > i)
                {
                    if (s[i] == '(' && s[j] == ')')
                    {
                        if (f[i + 1][j - 1] < f[i][j])
                        {
                            f[i][j] = f[i + 1][j - 1];
                            ans[i][j] = "(" + ans[i + 1][j - 1] + ")";
                        }
                    }
                    else if (s[i] == '[' && s[j] == ']')
                    {
                        if (f[i + 1][j - 1] < f[i][j])
                        {
                            f[i][j] = f[i + 1][j - 1];
                            ans[i][j] = "[" + ans[i + 1][j - 1] + "]";
                        }                            
                    }
                }
                for (int k = i; k < j; k++)
                {
                    if (f[i][k] + f[k + 1][j] < f[i][j])
                    {
                        f[i][j] = f[i][k] + f[k + 1][j];
                        ans[i][j] = ans[i][k] + ans[k + 1][j];
                    }
                }
            }
}

int main()
{
    while (scanf("%s", s) != EOF)
    {
        len = strlen(s);
        dp();
        cout << ans[0][len - 1] << endl;
    }
    return 0;
}
posted on 2007-08-27 15:55 Felicia 阅读(1217) 评论(3)  编辑 收藏 引用 所属分类: 动态规划
Comments
  • # re: [动态规划]pku1141
    l-y-p
    Posted @ 2008-03-03 11:36
    你的这个代码提交也WA，不知是怎么回事，自己也写了两个代码，也都WA，感觉都没错，但结果却WA  回复  更多评论   
  • # re: [动态规划]pku1141
    wobat
    Posted @ 2008-07-01 16:27
    对空的输入，要输出回车。。
    也缺了#include<string>。。
    其他的都对了  回复  更多评论   
  • # re: [动态规划]pku1141
    wwq
    Posted @ 2012-07-06 17:34
    你的这个代码提交WA了  回复  更多评论   

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Powered by:
C++博客
Copyright © Felicia