合肥网站制作,优秀手机网站模板图片,wordpress 获取菜单id,国内网站免费服务器题意#xff1a;给出一个表达式的子序列#xff0c;要你填充这个序列#xff0c;保证最终形成的序列长度最短#xff0c;也就是添加的括号最少 这个子序列要遵循括号匹配的原则。 分析#xff1a;转移方程dp[i][j]min(dp[i][k],dp[k1][j]).ikj.dp[1][1]1; dp[i][j…题意给出一个表达式的子序列要你填充这个序列保证最终形成的序列长度最短也就是添加的括号最少 这个子序列要遵循括号匹配的原则。 分析转移方程dp[i][j]min(dp[i][k],dp[k1][j]).ikj.dp[1][1]1; dp[i][j]表示i到j最少添加几个括号。同时用path[i][j]存插入括号的位置。递归输出。 1 #includecstdio2 #includecstring3 #includecmath4 #includecstdlib5 #includeiostream6 #includealgorithm7 #includevector8 #includemap9 #includequeue
10 #includestack
11 #includestring
12 #includeset
13 #define eps 1e-6
14 #define LL long long
15 #define clc(a,b) memset(a,b,sizeof(a))
16 const int maxd1e610;
17 using namespace std;
18 const int MAX 110;
19 const int INF 0x3f3f3f3f;
20 const int mod258280327;
21
22 int dp[MAX][MAX],path[MAX][MAX],len;
23 char str[MAX];
24
25 void output(int st ,int endd)
26 {
27 if(stendd)
28 return ;
29 else if(stendd)
30 {
31 if(str[st](||str[st]))
32 printf(());
33 else
34 printf([]);
35 }
36 else if(path[st][endd]-1)
37 {
38 printf(%c,str[st]);
39 output(st1,endd-1);
40 printf(%c,str[endd]);
41 }
42 else
43 {
44 output(st,path[st][endd]);
45 output(path[st][endd]1,endd);
46 }
47 }
48
49 int main()
50 {
51
52 while(gets(str)!NULL)
53 {
54 clc(dp,0);
55 lenstrlen(str);
56 for(int i0;ilen;i)
57 dp[i][i]1;
58 for(int l1;llen;l)
59 {
60 for(int i0;ilen-l;i)
61 {
62 int jil;
63 if(str[i](str[j])||str[i][str[j]])
64 {
65 dp[i][j]dp[i1][j-1];
66 path[i][j]-1;
67 }
68 else
69 dp[i][j]INF;
70 for(int ki;kj-1;k)
71 {
72 if(dp[i][j]dp[i][k]dp[k1][j])
73 {
74 dp[i][j]dp[i][k]dp[k1][j];
75 path[i][j]k;
76 }
77 }
78 }
79 }
80 output(0,len-1);
81 printf(\n);
82 }
83 return 0;
84 } View Code 转载于:https://www.cnblogs.com/ITUPC/p/4820389.html
