题目链接:
https://vjudge.net/problem/UVA-1626
题意:
题解:
dp[i][j]:= i~j需要最少的括号
区间dp：
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]);
if(match(s[i],s[j])) dp[i][j] = min(dp[i][j],dp[i+1][j-1]);
学到了一种dp打印解得方式
读入真坑啊…
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 1e5+10; 17 18 char s[maxn]; 19 int dp[105][105]; 20 21 bool match(char s1,char s2){ 22 if((s1=='(' && s2==')') || (s1=='['&&s2==']')) return true; 23 return false; 24 } 25 26 void print(int i,int j){ 27 if(i > j) return ; 28 if(i == j){ 29 if(s[i]=='(' || s[i]==')') printf("()"); 30 else printf("[]"); 31 return ; 32 } 33 int ans = dp[i][j]; 34 if(match(s[i],s[j]) && ans==dp[i+1][j-1]) { 35 printf("%c",s[i]); print(i+1,j-1); printf("%c",s[j]); 36 return ; 37 } 38 39 for(int k=i; k<j; k++){ 40 if(ans == dp[i][k]+dp[k+1][j]){ 41 print(i,k); print(k+1,j); 42 return ; 43 } 44 } 45 } 46 47 int main(){ 48 int T; 49 gets(s); 50 sscanf(s,"%d",&T); 51 gets(s); 52 53 while(T--){ 54 gets(s); 55 int n = strlen(s); 56 for(int i=0; i<n; i++){ 57 dp[i+1][i] = 0; 58 dp[i][i] = 1; 59 } 60 61 for(int len=1; len<n; len++){ 62 for(int i=0; i+len<n; i++){ 63 int j = i+len; 64 dp[i][j] = n; 65 if(match(s[i],s[j])) dp[i][j] = min(dp[i][j],dp[i+1][j-1]); 66 for(int k=i; k<j; k++){ 67 dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]); 68 } 69 } 70 } 71 72 print(0,n-1); 73 puts(""); 74 if(T) puts(""); 75 gets(s); 76 } 77 78 return 0; 79 }