wikioi 1251--括号

题目描述：给定n个变量，求乘积的表达式的个数。相邻元素相乘需要加*号。

思路：直接递归即可，ans[i][j] = ans[i][k]+ans[k+1][j]（i<=k<j）;对于单个字符而言，没有括号

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<vector>
 7 #include<string>
 8 using namespace std;
 9 
10 
11 vector<string> ans[20][15];
12 string a[15];
13 int n;
14 void dfs(int l, int r)
15 {
16     string s;
17     if (ans[l][r].size())
18         return;
19     if (l == r)
20         ans[l][r].push_back(a[l]);
21     else
22     {
23         for (int i = l; i < r; i++)
24         {
25             dfs(l, i);
26             dfs(i + 1, r);
27             int m1 = ans[l][i].size(), m2 = ans[i+1][r].size();
28             for (int j = 0; j < m1; j++)
29             {
30                 for (int k = 0; k < m2; k++)
31                 {
32                     if (l == i && i + 1 == r)
33                         s = "(" + ans[l][i][j] + "*" + ans[i + 1][r][k] + ")";
34                     else
35                     {
36                         s = "(" + ans[l][i][j] + ans[i+1][r][k] + ")";
37                     }
38                     ans[l][r].push_back(s);
39                 }
40             }
41         }
42     }
43 }
44 int main()
45 {
46     cin >> n;
47     for (int i = 1; i <= n; i++)
48         cin >> a[i];
49     dfs(1, n);
50     int m = ans[1][n].size();
51     for (int i = 0; i < m; i++)
52         cout << ans[1][n][i] << endl;
53     return 0;
54 }