1251 括號

?

?時間限制: 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)

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

輸入描述?Input Description

輸入文件第一行是一個數(shù)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)

思路

深搜

首先設(shè)一個動態(tài)數(shù)組vector<string>ans[11][11]。a[i][j][k]表示首單詞為i，末單詞為j的單詞串的總種類集合。

遞歸的思想。從大范圍往小范圍緊縮，也就是從整體（1到n的單詞串總種類集合）二分，先找到左側(cè)的種類再找右側(cè)種類，最后進(jìn)行拼接。

代碼

#include<iostream> #include<cstring> #include<vector> using namespace std; vector<string>ans[11][11]; int n; string s[12]; void dfs(int l,int r) {if(ans[l][r].size())return;if(l==r)ans[l][l].push_back(s[l]);else{for(int i=l;i<=r;i++){dfs(l,i);dfs(i+1,r);int n1=ans[l][i].size(),n2=ans[i+1][r].size();for(int j=0;j<n1;j++){for(int k=0;k<n2;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>>s[i];dfs(1,n);int m=ans[1][n].size();for(int i=0;i<m;i++)cout<<ans[1][n][i]<<endl; }

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/thmyl/p/6156241.html

總結(jié)

以上是生活随笔為你收集整理的codevs1251 括号的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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