移动网站建设书籍推荐,如何提交百度收录,网站开发 商标注册,沈阳专业做网站公司题意#xff1a;定义满足
1.空序列
2.#xff08;#xff09;#xff08;X#xff09;及括号和其括起来的合法序列
3.【】要求和#xff08;#xff09;相同
都是合法的串。 然后给定一段序列#xff0c;求添加最小的#xff08;#xff09;或【】使得序列合法。…
题意定义满足
1.空序列
2.X及括号和其括起来的合法序列
3.【】要求和相同
都是合法的串。 然后给定一段序列求添加最小的或【】使得序列合法。 思路 区间dp。以前做过用堆栈来判断合法性的题目这道题目同样是经典。
思想是不断分割小区间当出现X时应该转移到x即从dpij)转移到dpi1j-1
如果多于两个字符应该枚举中间点转移到最小的状态上。这一步应该一直进行无论上面是否成立反例【】【】
另输入输出略坑。 code #include bits/stdc.h
using namespace std;#define ft(i,s,t) for (int is;it;i)
#define frt(i,t,s) for (int it;is;i--)
#define cls(v,c) memset(v,c,sizeof(v))
const int INF0x3f3f3f3f;
const int N105;
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[i1][i]0;dp[i][i]1;}frt(i,n-2,0)ft(j,i1,n-1){dp[i][j]n;if (ok(s[i],s[j])) dp[i][j]min(dp[i][j],dp[i1][j-1]);ft(k,i,j-1) dp[i][j]min(dp[i][j],dp[i][k]dp[k1][j]);}
}void print(int i,int j)
{if (ij) return;if (ij){if (s[i](||s[i])) printf(());else printf([]);return;}int ansdp[i][j];if (ok(s[i],s[j])ansdp[i1][j-1]){printf(%c,s[i]);print(i1,j-1);printf(%c,s[j]);return;}ft(k,i,j-1)if (ansdp[i][k]dp[k1][j]){print(i,k); print(k1,j);return;}
}
int main()
{int T;scanf(%d,T);getchar();while (T--){gets(s);gets(s);nstrlen(s);sol();print(0,n-1);puts();if (T) puts();}
}
