pku1335 Digital Onion 遞歸
題意:定義括號(hào)序列:
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.
定義排序規(guī)則:
[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.
給出一個(gè)符號(hào)序列,求這個(gè)之后的一個(gè)符號(hào)序列是什么
思路:
首先要確定最小的符號(hào)序列為:()()()...
然后就是轉(zhuǎn)化方法:
對(duì)于一個(gè)符號(hào)序列(inside)outside,首先看outside能否+1,不行的話看inside能否+1,同時(shí)將outside置為最小值形式,再不行的話當(dāng)outside不為空的時(shí)候?qū)nside的weight+1,outside's weight-1,將兩部分都轉(zhuǎn)化為最小值形式。
以上描述的是一個(gè)遞歸過(guò)程~當(dāng)然,考慮一種特殊情況,如果整個(gè)式子無(wú)法進(jìn)行+1操作,只能將整個(gè)式子的weight+1,然后化為最小值形式。
發(fā)現(xiàn)java的string竟然是值傳遞,非常的蛋疼。。我喜歡java的String,沒辦法,只好用C++的string。。。這種字符串處理的題目string是非常給力的~
代碼:
1
# include <iostream>
2
# include <string>
3
# include <cstring>
4
using namespace std;
5
string str;
6
void 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
}
17
bool 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
}
44
int 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
}

2

3

4

5

6

7



8

9

10

11

12

13

14

15

16

17

18



19

20

21



22

23

24

25



26

27

28

29

30

31



32

33

34

35

36



37

38

39

40

41

42

43

44

45



46

47

48

49



50

51

52



53

54

55

56

57

58

59

60

61

62

63

64

posted on 2011-01-25 01:01 yzhw 閱讀(258) 評(píng)論(0) 編輯 收藏 引用 所屬分類: DP