亚洲激情一区二区,亚洲国产精品成人综合,午夜久久tv

江蘇大學

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>
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

}

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

只有注冊用戶登錄后才能發表評論。


相關文章: pku3903 最長遞增字串的單調性優化 pku 3998 Land Division DP斜率優化 The 36th ACM/ICPC Asia Regional Dalian Online Contest 大連2011ICPC網絡賽個人題解 pku3124 The Bookcase 擴展背包好題 pku1202 Family DAG圖上的概率DP pku 1946 Cow Cycling 非常好的DP pku1948 Triangular Pastures DP+枚舉。海倫公式 pku1335 Digital Onion 遞歸 pku1332 Finding Liars DP 經典好題 pku1337 A Lazy Worker 很詭異的DP

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理