pku1335 Digital Onion 递归

题意：
定义括号序列：
Definition: Null parenthesis is a DO. Especially, we call this the Null DO. 
Definition: "( )" is a DO. Especially, we call this the primitive DO. 
Definition: If both A and B are DOs, then the combined form of "(A)B" is also a DO, where we call A the inside of the DO and B the outside of the DO. 
定义排序规则：
[Rule1]: The more weight, the more expensive. 
[Rule2]: If the weights of two DOs are equal, then the price depends on the inside DO of the two DOs. 
[Rule3]: If the weights of two DOs are the same and the prices of the inside DOs are equal, then the price depends on the outside DO of the two DOs. 
给出一个符号序列，求这个之后的一个符号序列是什么

思路：
首先要确定最小的符号序列为：（）（）（）...
然后就是转化方法：
对于一个符号序列(inside)outside，首先看outside能否+1，不行的话看inside能否+1，同时将outside置为最小值形式，再不行的话当outside不为空的时候将inside的weight+1,outside's weight-1，将两部分都转化为最小值形式。
以上描述的是一个递归过程~当然，考虑一种特殊情况，如果整个式子无法进行+1操作，只能将整个式子的weight+1,然后化为最小值形式。

发现java的string竟然是值传递，非常的蛋疼。。我喜欢java的String，没办法，只好用C++的string。。。这种字符串处理的题目string是非常给力的~

代码：
 1# include <iostream>
 2# include <string>
 3# include <cstring>
 4using namespace std;
 5string str;
 6void make(int s,int e,int type)
 7{
 8    int c=0;
 9    for(int i=s;i<e;i++)
10        if(str[i]=='(')
11            c++;
12    c+=type;
13    string res="";
14    for(int i=0;i<c;i++) res+="()";
15    str=str.substr(0,s)+res+str.substr(e,str.length()-e);
16}
17bool solve(int s,int e)
18{
19    if(s==e) return false;
20    else
21    {
22        int c=-1,end;
23        for(end=s+1;end<e&&c;end++)
24            switch(str[end])
25            {
26            case '(':c--;break;
27            case ')':c++;break;
28            };
29        if(solve(end,e)) return true;
30        else if(solve(s+1,end-1))
31        {
32            make(end,e,0);
33            return true;
34        }
35        else if(end!=e)
36        {
37            make(end,e,-1);
38            make(s+1,end-1,1);
39            return true;
40        }
41        else return false;
42    }
43}
44int main()
45{
46    int test;
47    cin>>test;
48    while(test--)
49    {
50        str.clear();
51        while(true)
52        {
53            string tmp;
54            cin>>tmp;
55            if(tmp=="$") break;
56            str+=tmp;
57        }
58        if(!solve(0,str.length())) make(0,str.length(),1);
59        for(int i=0;i<str.length();i++)
60            cout<<str[i]<<" ";
61        cout<<"$"<<endl;
62    }
63    return 0;
64}

posted on 2011-01-25 01:01 yzhw 阅读(304) 评论(0)  编辑 收藏 引用 所属分类: DP


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2011年2月>
日一二三四五六
303112345
6789101112
13141516171819
20212223242526
272812345
6789101112

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜