URAL 1183.Brackets Sequence （ DP+记录路径）

本文主要是介绍URAL 1183.Brackets Sequence （ DP+记录路径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：加入最少数量的括号使得这个括号序列合法。

思路：DP

dp[ i ][ j ]表示 区间[ i , j ] 变成合法需要加的最少括号数。

而，要求dp[ i ][ j ]有三种情况

(1) i==j : dp[ i ][ j ]=1 就是加上对应的括号

(2) ch[ i ] 和 ch[ j ] 不能配对 : min(dp[i][k]+dp[k+1][j]) for k=i,i+1,...,j-1

(3) ch[ i ] 和 ch[ j ] 能配对：

如果i+1==j    dp[i][j]=0;

否则 dp[i][j] = 将 dp[i+1][j-1]  与 (2) 中的情况相对比，求最小。

这就求出了数量。要显示出来，就DP的时候，同步记录操作。

op[ i ][ j ] = 0 :表示加上与这个括号对应的括号

op[ i ][ j ] =-1:表示ch[ i ] 与 ch[ j ] 是一对括号

op[ i ][ j ] =k>0: 表示分成两组：[ i , k ] 和 [ k+1 , j ]

然后最后递归输出就行了。

DP部分代码：

for(int i=n;i>0;--i){for(int j=i;j<=n;++j){if(i==j){dp[i][j]=1;op[i][j]=0;//0 means add the one that matchescontinue;}int K=i,ANS=dp[i][K]+dp[K+1][j];for(int k=K+1;k <j;++k){if(dp[i][k]+dp[k+1][j]<ANS){ANS=dp[i][k]+dp[k+1][j];K=k;}}dp[i][j]=ANS;op[i][j]=K;//positive value means to split at op[i][j] if(ch[i]=='['&&ch[j]==']'||ch[i]=='('&&ch[j]==')'){if(i+1==j){dp[i][j]=0;op[i][j]=-1;}else if(dp[i+1][j-1]<dp[i][j]) {dp[i][j]=dp[i+1][j-1];op[i][j]=-1;//-1 means ch[i] and ch[j] matches}}}
}

显示部分代码：

void Show(int i,int j){if(~op[i][j]){if(op[i][j]){//positive value : split at op[i][j]Show(i,op[i][j]);Show(op[i][j]+1,j);}else{//op[i][j]=0 :add the one that matchesif(ch[i]=='('||ch[i]==')') printf("()");else printf("[]");}}else{//op[i][j] = -1 ：ch[i] and ch[j] matches printf("%c",ch[i]);if(i+1!=j) Show(i+1,j-1);printf("%c",ch[j]);}
}

这篇关于URAL 1183.Brackets Sequence （ DP+记录路径）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---