亚洲伊人久久精品影院,伊人精品久久久久7777,国产美女久久精品香蕉69

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是非常給力的~

代碼：

# 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 閱讀(258) 評(píng)論(0) 編輯收藏引用所屬分類: DP

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

pku1335 Digital Onion 遞歸

導(dǎo)航

統(tǒng)計(jì)

公告

留言簿(1)

隨筆分類(227)

文章分類(2)

OJ

最新隨筆

搜索

積分與排名

最新評(píng)論

閱讀排行榜