题意：给出一个表达式的子序列，要你填充这个序列，保证最终形成的序列长度最短，也就是添加的括号最少
这个子序列要遵循括号匹配的原则。
分析：转移方程dp[i][j]=min(dp[i][k],dp[k+1][j]).i<=k<j.dp[1][1]=1;
dp[i][j]表示i到j最少添加几个括号。同时用path[i][j]存插入括号的位置。递归输出。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<cstdlib> 5 #include<iostream> 6 #include<algorithm> 7 #include<vector> 8 #include<map> 9 #include<queue> 10 #include<stack> 11 #include<string> 12 #include<set> 13 #define eps 1e-6 14 #define LL long long 15 #define clc(a,b) memset(a,b,sizeof(a)) 16 const int maxd=1e6+10; 17 using namespace std; 18 const int MAX = 110; 19 const int INF = 0x3f3f3f3f; 20 const int mod=258280327; 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(st>endd) 28 return ; 29 else if(st==endd) 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(st+1,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 len=strlen(str); 56 for(int i=0;i<len;i++) 57 dp[i][i]=1; 58 for(int l=1;l<len;l++) 59 { 60 for(int i=0;i<=len-l;i++) 61 { 62 int j=i+l; 63 if(str[i]=='('&&str[j]==')'||str[i]=='['&&str[j]==']') 64 { 65 dp[i][j]=dp[i+1][j-1]; 66 path[i][j]=-1; 67 } 68 else 69 dp[i][j]=INF; 70 for(int k=i;k<=j-1;k++) 71 { 72 if(dp[i][j]>dp[i][k]+dp[k+1][j]) 73 { 74 dp[i][j]=dp[i][k]+dp[k+1][j]; 75 path[i][j]=k; 76 } 77 } 78 } 79 } 80 output(0,len-1); 81 printf(" "); 82 } 83 return 0; 84 }