1251 括號(hào)

?時(shí)間限制: 1 s ?空間限制: 128000 KB ?題目等級(jí) : 黃金 Gold 題目描述?Description

　　　　計(jì)算乘法時(shí)，我們可以添加括號(hào)，來改變相乘的順序，比如計(jì)算　　?　　?　　?　　?　　X1,?X2,?X3,?X4,?…,?XN的積，可以

?　　(X1(X2(X3(X4(...(XN-1*XN)...)))))

?　　?:::

?　　:::

?　　(((...(((X1*X2)X3)X4)...)XN-1)XN)

?　　你的任務(wù)是編程求出所有這樣的添括號(hào)的方案。

輸入描述?Input Description

　　　　輸入文件第一行是一個(gè)數(shù)n（1<=n<=10），表示有n個(gè)變量，之后N行每行一個(gè)變量的名字。

輸出描述?Output Description

　　　　輸出所有的添加括號(hào)的方案。注意：單個(gè)字符不要加括號(hào)，兩個(gè)字符相乘中間要有乘號(hào)。

樣例輸入?Sample Input

4

North?

South?

East?

West

樣例輸出?Sample Output

(North(South(East*West)))

(North((South*East)West))

((North*South)(East*West))

((North(South*East))West)

(((North*South)East)West)

數(shù)據(jù)范圍及提示?Data Size & Hint

分類標(biāo)簽?Tags?點(diǎn)此展開?

?

So,具體思路見題解，好了不多說了，上題解：

?

#include<iostream> #include<string> #include<vector> using namespace std; vector<string>ans[12][12]; string str[11]; int n; void dfs(int l,int r) // l,r單詞的分割數(shù)目,初始還沒求得所要的串，結(jié)果為空 {if(ans[l][r].size()) // 存放第一個(gè) 首單詞 位置為 l 尾單詞位置為r的 單詞串return;if(l==r) // 僅有單個(gè)單詞,放到對(duì)應(yīng)的位置上 ans[l][l].push_back(str[l]);else{for(int i=l;i<r;i++){dfs(l,i);dfs(i+1,r); // 遞歸求解，各左右子串的劃分形式。int sl=ans[l][i].size(),sr=ans[i+1][r].size();for (int j=0;j<sl;j++){ // 進(jìn)行連接運(yùn)算for (int k=0; k<sr;k++){string s;s ="("+ans[l][i][j];if (r-l==1) // s+="*"; // 做連接運(yùn)算時(shí)加*號(hào)s+=(ans[i+1][r][k]+")");ans[l][r].push_back(s); // 存入一種結(jié)果 }}}} } int main() {cin>>n;for (int i=1;i<=n;i++)cin>>str[i];dfs(1,n);int m=ans[1][n].size();for (int i=0;i<m;i++)cout<<ans[1][n][i]<<endl; // 輸出所有可能結(jié)果return 0; }

如果對(duì)你有所幫助，別忘了加好評(píng)哦；么么噠！！下次見！88

轉(zhuǎn)載于:https://www.cnblogs.com/cangT-Tlan/p/6159034.html

總結(jié)

以上是生活随笔為你收集整理的1251 括号（递归小练）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。