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, 
0sizeof(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 阅读(1195) 评论(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   知识库   博问   管理