| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 494 人关注过本帖
标题:DP问题一定要用DP吗?
只看楼主 加入收藏
bbb222
Rank: 2
等 级:论坛游民
帖 子:31
专家分:54
注 册:2012-11-17
结帖率:77.78%
收藏
已结贴  问题点数:20 回复次数:1 
DP问题一定要用DP吗?
Let us define a regular brackets sequence in the following way:

Empty sequence is a regular sequence.
If S is a regular sequence, then (S) and [S] are both regular sequences.
If A and B are regular sequences, then AB is a regular sequence.
For example, all of the following sequences of characters are regular brackets sequences:

(), [], (()), ([]), ()[], ()[()]

And all of the following character sequences are not:

(, [, ), )(, ([)], ([(]

Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1a2...an is called a subsequence of the string b1b2...bm, if there exist such indices 1 ≤ i1 < i2 < ... < in ≤ m, that aj=bij for all 1 ≤ j ≤ n.

Input
The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.

Output
Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.

Sample input
([(]
Sample output for the sample input
()[()]
#include <iostream>

using namespace std;

int main()
{
    string str,s;
    while(cin >> str)
    {
        int leng,a,b,c,d;
        a=0;b=0;c=0;d=0;
        leng = str.length();
        for(int i = 0; i < leng; i++)
            s[i] = str[i];
        for(int k = 0; k < leng-1; k++)
            for(int j = 0; j < leng-k-1; j++)
            {
                if(str[j] == '['&&str[j+k+1] == ']')
                {
                    str[j] = '1';
                    str[j+k+1] = '1';
                }
                if(str[j] == '{'&&str[j+k+1] == '}')
                {
                    str[j] = '1';
                    str[j+k+1] = '1';
                }
            }
        for(int l = 0; l < leng; l++)
        {
            if(str[l] == '['|| str[l] == ']')
                cout << "[]";
            else if(str[l] == '{'|| str[l] == '}')
                cout << "{}";
            else
                cout << s[l];

        }
        cout << endl;
    }

    return 0;
}
我的代码一直通过不了...
求教DP要如何用...
搜索更多相关主题的帖子: character following sequence regular 
2012-12-08 01:53
w527705090
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:11
帖 子:441
专家分:1882
注 册:2011-6-28
收藏
得分:20 
DP?见识短浅啊。。。不知道这是什么玩意。。。
帮顶了

有心者,千方百计;无心者,千难万难。
2012-12-09 01:09
快速回复:DP问题一定要用DP吗?
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.035665 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved