本文主要是介绍Codeforces 1272 F Two Bracket Sequences —— bfs+dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
This way
题意：
现在有两个串，让你构造一个母串使得这两个串是这个串的子串，并且这个串要平衡，长度最小。输出这个串
题解：
不太会做，看了题解才发现原来还有这种思考方法，不要将思维固定。
dp[i][j][k]表示第一个串到第i个位置，第二个串到第j个位置时，左括号比右括号多k个的最少长度
那么每次新增一个位置的时候只有两种情况，判断一下是否出现过。用一个pre数组记录每个情况新增的括号是什么，和从那里转移过来的即可。并且注意左右括号之间的差不会超过200
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int dp[N][N][N];
char s1[N],s2[N];
int l1,l2;
struct node
{int i,j,k;char s;
}pre[N][N][N];
void bfs(){queue<node>Q;Q.push({0,0,0,' '});dp[0][0][0]=0;while(!Q.empty()){node u=Q.front(),ne;Q.pop();ne.i=u.i+(u.i+1<=l1&&s1[u.i+1]=='(');ne.j=u.j+(u.j+1<=l2&&s2[u.j+1]=='(');if(dp[ne.i][ne.j][u.k+1]==-1&&u.k+1<=200){dp[ne.i][ne.j][u.k+1]=dp[u.i][u.j][u.k]+1;pre[ne.i][ne.j][u.k+1]={u.i,u.j,u.k,'('};Q.push({ne.i,ne.j,u.k+1,' '});}ne.i=u.i+(u.i+1<=l1&&s1[u.i+1]==')');ne.j=u.j+(u.j+1<=l2&&s2[u.j+1]==')');if(dp[ne.i][ne.j][u.k-1]==-1&&u.k-1>=0){dp[ne.i][ne.j][u.k-1]=dp[u.i][u.j][u.k]+1;pre[ne.i][ne.j][u.k-1]={u.i,u.j,u.k,')'};Q.push({ne.i,ne.j,u.k-1,' '});}}
}
void dfs(node x){if(x.i==0&&x.j==0&&x.k==0){printf("%c",x.s);return ;}dfs(pre[x.i][x.j][x.k]);printf("%c",x.s);
}
int main()
{memset(dp,-1,sizeof(dp));scanf("%s%s",s1+1,s2+1);l1=strlen(s1+1),l2=strlen(s2+1);bfs();node now=pre[l1][l2][0];dfs(now);return 0*printf("\n");
}这篇关于Codeforces 1272 F Two Bracket Sequences —— bfs+dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
