題意：定義滿足

1.空序列

2.（）（X）及括號和其括起來的合法序列

3.【】要求和（）相同

都是合法的串。

然后給定一段序列，求添加最小的（）或【】使得序列合法。

思路： 區間dp。以前做過用堆棧來判斷合法性的題目，這道題目同樣是經典。

思想是不斷分割小區間，當出現（X）時，應該轉移到x，即從dp（i，j)轉移到dp（i+1，j-1）

如果多于兩個字符應該枚舉中間點轉移到最小的狀態上。這一步應該一直進行，無論上面是否成立（反例：【】【】）

另：輸入輸出略坑。

code：

#include <bits/stdc++.h> using namespace std;#define ft(i,s,t) for (int i=s;i<=t;i++) #define frt(i,t,s) for (int i=t;i>=s;i--) #define cls(v,c) memset(v,c,sizeof(v)) const int INF=0x3f3f3f3f; const int N=105; char s[N]; int dp[N][N],n;bool ok(char a,char b) {return (a=='('&&b==')')||(a=='['&&b==']'); } void sol() {ft(i,0,n-1){dp[i+1][i]=0;dp[i][i]=1;}frt(i,n-2,0)ft(j,i+1,n-1){dp[i][j]=n;if (ok(s[i],s[j])) dp[i][j]=min(dp[i][j],dp[i+1][j-1]);ft(k,i,j-1) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);} }void print(int i,int j) {if (i>j) return;if (i==j){if (s[i]=='('||s[i]==')') printf("()");else printf("[]");return;}int ans=dp[i][j];if (ok(s[i],s[j])&&ans==dp[i+1][j-1]){printf("%c",s[i]);print(i+1,j-1);printf("%c",s[j]);return;}ft(k,i,j-1)if (ans==dp[i][k]+dp[k+1][j]){print(i,k); print(k+1,j);return;} } int main() {int T;scanf("%d",&T);getchar();while (T--){gets(s);gets(s);n=strlen(s);sol();print(0,n-1);puts("");if (T) puts("");} }

總結

以上是生活随笔為你收集整理的uva 1626——Brackets sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。