?時間限制: 1 s
?空間限制: 128000 KB
?題目等級 : 黃金 Gold
題目描述?Description
計算乘法時，我們可以添加括號，來改變相乘的順序，比如計算 ? ? ? ? X1,?X2,?X3,?X4,?…,?XN的積，可以
? (X1(X2(X3(X4(...(XN-1*XN)...)))))
? ?:::
? :::
? (((...(((X1*X2)X3)X4)...)XN-1)XN)
? 你的任務是編程求出所有這樣的添括號的方案。
輸入描述?Input Description
輸入文件第一行是一個數n（1<=n<=10），表示有n個變量，之后N行每行一個變量的名字。
輸出描述?Output Description
輸出所有的添加括號的方案。注意：單個字符不要加括號，兩個字符相乘中間要有乘號。
樣例輸入?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)
數據范圍及提示?Data Size & Hint
分類標簽?Tags?點此展開?
?
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單詞的分割數目,初始還沒求得所要的串，結果為空 {if(ans[l][r].size()) // 存放第一個 首單詞 位置為 l 尾單詞位置為r的 單詞串return;if(l==r) // 僅有單個單詞,放到對應的位置上 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++){ // 進行連接運算for (int k=0; k<sr;k++){string s;s ="("+ans[l][i][j];if (r-l==1) // s+="*"; // 做連接運算時加*號s+=(ans[i+1][r][k]+")");ans[l][r].push_back(s); // 存入一種結果 }}}} } 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; // 輸出所有可能結果return 0; }
