给定一个长度为 n 的括号序列 S，其中有些位置上的字符缺失被换为 ∗，询问存在多少种将 S 中的 ∗ 替换为 ( 或 ) 的方案，使得 S仍然合法。若存在方案，输出字典序最小和最大的方案。
对于一个括号序列 A 而言，合法的定义为：
‘A = ()’ 是合法的
如果存在一个合法的 B，使得 ‘A = (B)’ ，则 A 是合法的
如果存在合法的 B,C，使得 ‘A = B + C’，其中 + 表示字符串的拼接操作，则 A 是合法的
输入格式：
输入一行长度为 n(1≤n≤5×103) 的括号序列 S，其中只包含 (,),∗ 三种字符
输出格式
第一行输出一个整数 ans，表示在模 998244353 意义下的方案数
若存在方案，则在接下来一行输出字典序最小方案，再下来一行输出字典序最大方案
输入样例：
*)(**())(*
输出样例：
2
()(()())()
()()(())()
一、深度搜索
1、无脑深搜 超时，且有的答案是错的 拿2分
//无脑深搜 超时，且有的答案是错的 拿2分
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod = 988244353;
string strmin,strmax;
bool flag = true;
bool is_bracket(string s)
{
int len = 0;
for(int i=0; i<s.size(); i++) {
if(s[i]=='(') len++;
else {
if(!len) return false;
len--;
}
}
if(!len)
return true;
}
ll dfs(int index,string s)
{
if(index == s.size()) {
if(is_bracket(s)) {
if(flag) {//深搜第一个合法的即为字典序最小
strmin = s;
flag = false;
}
strmax = s;//深搜最后一个即为字典序最大
return 1;
} else return 0;
}
if(s[index] == '*') {
s[index] = '(';
ll ans = dfs(index+1,s)%mod;
s[index] = ')';
return (ans+dfs(index+1,s))%mod;
}
return dfs(index+1,s)%mod;
}
//卡特兰数：1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190
int main()
{
string str;
cin>>str;
cout<<dfs(0,str)<<endl;
cout<<strmin<<endl<<strmax<<endl;
return 0;
}
2、DFS 稍微剪枝 会超时 得3分
//DFS 稍微剪枝 会超时 得3分
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod = 988244353;
string strmin,strmax;
int numl = 0,numr = 0,len,cntl = 0,cntr = 0;
bool flag = true;
bool is_bracket(string s)//判断当前括号序列是否合法（不一定要用栈）
{
int len = 0;
for(int i=0; i<s.size(); i++) {
if(s[i]=='(') len++;
else {
if(!len) return false;
len--;
}
}
if(!len)
return true;
}
ll dfs(int index,string &s)//s为引用，出dfs需要恢复原来序列
{
if(index == s.size()) {
if(is_bracket(s)) {
//cout<<s<<endl;
if(flag) {
strmin = s;
flag = false;
}
strmax = s;
return 1;
} else return 0;
}
if(s[index] == '*') {
ll ans=0;
if((numl+cntl) < len) {
s[index] = '(';
cntl++;
ans = dfs(index+1,s)%mod;
cntl--;
s[index] = '*';
}
if((numr+cntr) < len) {
s[index] = ')';
cntr++;
ans = (ans+dfs(index+1,s))%mod;
cntr--;
s[index] = '*';
}
return ans;
}
return dfs(index+1,s)%mod;
}
//卡特兰数：1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190
int main()
{
//string str = "*)(**())(*"; //"**********";
string str;
cin>>str;
for(int i=0; i<str.size(); i++) { //计算已有的括号数
if(str[i] == '(') numl++;
if(str[i] == ')') numr++;
}
len = str.size()/2;
cout<<dfs(0,str)<<endl;
cout<<strmin<<endl<<strmax<<endl;
return 0;
}
// *)(**())(* 样例 2
//******************** 10对 16796
//************************************ 18对
//(**)*()(*(***(**))*****(()****)* 16151
3、DFS 进一步剪枝，并省略最终判断 超时 得3分
这里思路初想感觉有些巧妙，但确实有特例过不了，并且这题深度搜索本来有超时
//DFS 进一步剪枝，并省略最终判断 超时3分
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod = 988244353;
string strmin,strmax;
int len,numl = 0,numr = 0,cntl = 0,cntr = 0,nowl = 0,nowr =0;
bool flag = true;
ll dfs(int index,string s)
{
ll ans=0;
if(index == s.size()) {
if(flag) {
strmin = s;
flag = false;
}
strmax = s;
return 1;
}
if(s[index] == '(') nowl++;
if(s[index] == ')') nowr++;
if(s[index] == '*') {
if((numl+cntl) < len&&index!=s.size()-1) {
s[index] = '(';
cntl++;
ans = dfs(index+1,s)%mod;
cntl--;
}
//当前)少于当前(，即可保证括号合法 //补充：有特例不满足，该思路有误。
if((numr+cntr) < len && (cntr+nowr)<(cntl+nowl) ) {
if(index <s.size()-1&&s[index+1] == ')'&&(cntr+nowr+1)==(cntl+nowl)) return ans;
s[index] = ')';
cntr++;
ans = (ans+dfs(index+1,s))%mod;
cntr--;
}
return ans;
}
ans = (ans+ dfs(index+1,s))%mod;
if(s[index] == '(') nowl--;
if(s[index] == ')') nowr--;
return ans;
}
//卡特兰数：1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190
int main()
{
//string str = "*)(**())(*"; //"**********";
string str;
cin>>str;
for(int i=0; i<str.size(); i++) {
if(str[i] == '(') numl++;
if(str[i] == ')') numr++;
}
len = str.size()/2;
cout<<dfs(0,str)<<endl;
cout<<strmin<<endl<<strmax<<endl;
return 0;
}
//(**)*()(*(***(**))*****(()****)* 16对 输出两种经典情况22035，16359, 但应为16151
//(()*)***)))**) 该输出有误！
二、提交的动态规划方法
（下面写的内容，是做完这个题二十天后写的，确实也没啥钻研的兴致了…人生匆匆向前行，一件事接着一件事…）
1、凭感觉写的第一个版本的DP
#include <bits/stdc++.h>
#define de(a) cout << #a << " = " << a << endl
using namespace std;
typedef long long ll;
ll dp[2501][2501][2];
int cntl[2500],cntr[2500];
int mod = 998244353;
int main()
{
int n=0,numl=0,numr=0;
string str;
cin>>str;
memset(dp,0,sizeof(dp));
for(int i=0; i<str.size(); i++) {
if(str[i]=='*') {
cntl[n] = numl;
cntr[n] = numr;
n++;
}
if(str[i]=='(') numl++;
if(str[i]==')') numr++;
}
int len = str.size()/2;
int nowl = len-numl,nowr = len-numr;
dp[nowl-1][nowr][0] = 1;
if(cntl[0]>cntr[0]) dp[nowl][nowr-1][1] = 1;
for(int i=nowl; i>=0; i--) {
for(int j=nowr; j>=0; j--) {
if(i>0) dp[i-1][j][0] += (dp[i][j][0]+dp[i][j][1])%mod;
int index = nowl-i+nowr-j;
if(j>0 &&(nowl-i+cntl[index])>(nowr-j+cntr[index]))
dp[i][j-1][1] += (dp[i][j][0]+dp[i][j][1])%mod;
}
}
ll sum = (dp[0][0][0]+dp[0][0][1])%mod;
cout<<sum<<endl;
string s1=str,s2=str;
for(int i=0; i<n; i++) {
if(nowl>0) {
s1[cntl[i]+cntr[i]+i] = '(';
nowl--;
} else s1[cntl[i]+cntr[i]+i] = ')';
}
cout<<s1<<endl;
int l=0,r=0;
for(int i=0; i<n-1; i++) {
if(cntl[i]+l > cntr[i]+r &&cntl[i+1]+l>=cntr[i+1]+r+1 && numr+r<len) {//有误！
s2[cntl[i]+cntr[i]+i] = ')';
r++;
} else {
s2[cntl[i]+cntr[i]+i] = '(';
l++;
}
}
s2[cntl[n-1]+cntr[n-1]+n-1] = numr+r<len?')':'(';
cout<<s2<<endl;
return 0;
}
2、自认为会对DP版
好像拿了三分
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[5001][5001][2]= {0}; //在第i个位置有j个多余( ，当前选(或)的方案数
int vis[5001]; //求最大值时，遍历标记数组
char s[5001],mins[5001],maxs[5001];
ll md=998244353;
int main()
{
//总长度，*()的数目 ,输入非法性标志
int n=0,snum=0,lnum=0,rnum=0,fl=0;
scanf("%s",s);
n=strlen(s);
if(s[0]=='*') s[0]='(';
if(s[n-1]=='*') s[n-1]=')';
for(int i=0; i<n; i++) {
mins[i]=s[i];
maxs[i]=s[i];
if(s[i]=='(') {
lnum++;
} else if(s[i]==')') {
rnum++;
if(rnum>(lnum+snum)) {
fl=-1;
break;
}
} else {
snum++;
}
}
int d=abs(lnum-rnum);
if(d>snum||(snum-d)%2==1) fl=-1;
if(fl==-1) { //输入不合法
printf("0\n");
return 0;
}
//1、动态规划求总方案数
dp[0][1][0]=1;//第1个位置有1个多余的(，此时放的是(
for(int i=1; i<n; i++) {
if(s[i]=='(') {
for(int j=1; j<n; j++) {
dp[i][j][0]=dp[i-1][j-1][0]+dp[i-1][j-1][1];
dp[i][j][1]=0;
dp[i][j][0]%=md;
}
} else if(s[i]==')') {
for(int j=1; j<n; j++) {
dp[i][j-1][0]=0;
dp[i][j-1][1]=dp[i-1][j][0]+dp[i-1][j][1];
dp[i][j-1][1]%=md;
}
} else {
for(int j=1; j<n; j++) {
dp[i][j][0]=dp[i-1][j-1][0]+dp[i-1][j-1][1];
dp[i][j-1][1]=dp[i-1][j][0]+dp[i-1][j][1];
dp[i][j][0]%=md;
dp[i][j-1][1]%=md;
}
}
}
//2、字典序最小
mins[n]=s[n],maxs[n]=s[n];
int minl=lnum;
int hf=n/2;
for(int i=0; i<n; i++) {//贪心，->优先选(
if(mins[i]=='*') {
if(minl<hf) {
mins[i]='(';
minl++;
} else {
mins[i]=')';
}
}
}
//3、字典序最大
for(int i=0; i<n; i++) {
if(vis[i]==0&&maxs[i]!='*') {
vis[i]=1;
if(maxs[i]=='(') {//->找到其对应)
for(int j=i+1; j<n; j++) {
if(vis[j]==0&&(maxs[j]=='*'||maxs[j]==')')) {
maxs[j]=')';
vis[j]=1;
break;
}
}
} else if(maxs[i]==')') {//<-找其对应(
for(int j=i-1; j>=0; j--) {
if(vis[j]==0&&(maxs[j]=='*'||maxs[j]=='(')) {
maxs[j]='(';
vis[j]=1;
break;
}
}
}
}
}
int x=0;//对于剩余*,先左再右交替进行
for(int i=0; i<n; i++) {
if(maxs[i]=='*') {
if(x==0) {
maxs[i]='(';
x++;
} else {
maxs[i]=')';
x--;
}
}
}
printf("%lld\n%s\n%s\n",dp[n-1][0][1]%md,mins,maxs);
return 0;
}
三、他山之石（DP，全对）
之前想着花时间钻研来着，…也不能完全归因于拖延症啥的，毕竟，毕竟，生活没有最优解，但是有优先级！
1、用时约56ms
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define dd(a) cout << #a << " = " << a << ' '
#define de(a) cout << #a << " = " << a << endl
const int N = 5010, MOD = 998244353;
ll f[2][N];
int n;
int suf_left[N], suf_right[N];
bool first = true;
char s[N], t[N], s1[N], s2[N];
ll solve(){
f[0][0] = 1;
for(int i = 1; i <= n; i++){
int idx = i & 1;
if(s[i] == '('){
f[idx][0] = 0;
for(int j = 1; j <= n; j++){
f[idx][j] = f[1 - idx][j - 1];
}
}
else {
f[idx][0] = f[1 - idx][1];
for(int j = 1; j <= i; j++){
if(s[i] == ')')
f[idx][j] = f[1 - idx][j + 1];
else
f[idx][j] = (f[1 - idx][j - 1] + f[1 - idx][j + 1]) % MOD;
}
}
}
return f[n&1][0];
}
void dfs(int pos, int cnt, int k, int left, int right){
if(cnt < 0 || !first || left + suf_left[pos] > n / 2 || right + suf_right[pos] > n / 2) return ;
if(pos == n + 1){
if(cnt == 0){
// printf("%s\n", s + 1);
if(first){
first = false;
if(k)
copy(s + 1, s + 1 + n, s1);
else
copy(s + 1, s + 1 + n, s2);
}
return ;
}
return ;
}
if(s[pos] == '(') dfs(pos + 1, cnt + 1, k, left + 1, right);
else if(s[pos] == ')') dfs(pos + 1, cnt - 1, k, left, right + 1);
else{
if(k){
s[pos] = '(';
dfs(pos + 1, cnt + 1, k, left + 1, right);
s[pos] = ')';
dfs(pos + 1, cnt - 1, k, left, right + 1);
}
else{
s[pos] = ')';
dfs(pos + 1, cnt - 1, k, left, right + 1);
s[pos] = '(';
dfs(pos + 1, cnt + 1, k, left + 1, right);
}
s[pos] = '*';
}
}
int main()
{
scanf("%s", s + 1);
n = strlen(s + 1);
for(int i = n; i >= 1; i--){
suf_left[i] = suf_left[i + 1] + (s[i] == '(');
suf_right[i] = suf_right[i + 1] + (s[i] == ')');
}
ll res = solve();
cout << res << '\n';
if(res){
dfs(1, 0, 1, 0, 0);
first = true;
dfs(1, 0, 0, 0, 0);
printf("%s\n%s\n", s1, s2);
}
return 0;
}
2、用时约300ms
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
#include<stack>
#include<map>
#include <algorithm>
#define rep(i,l,r) for(int i=(l);i<(r);i++)
#define per(i,l,r) for(int i=(r-1);i>=(l);i--)
#define ll long long
using namespace std;
ll dp[5005][5005];
int b[5005],c[5005];
ll mod=998244353;
string s,mi,mx;
int l,f=0;
void find1(int x,int num,int cnt)
{
if(f==1)return ;
if(num<0)return ;
if((cnt+b[x])>l/2)return ;
if(num>(l-x))return ;
if(x==l)
{
if(num==0)f=1;
return ;
}
if(x==0)find1(x+1,num+1,cnt+1);
else if(s[x]=='(')find1(x+1,num+1,cnt+1);
else if(s[x]==')')find1(x+1,num-1,cnt);
else
{
mi[x]='(';
find1(x+1,num+1,cnt+1);
if(f==1)return ;
mi[x]=')';
find1(x+1,num-1,cnt);
}
}
void find2(int x,int num,int cnt)
{
if(f==1)return ;
if(num<0)return ;
if((cnt+c[x])>l/2)return ;
if(num>(l-x))return ;
if(x==l)
{
if(num==0)f=1;
return ;
}
if(x==0)find2(x+1,num+1,cnt);
else if(s[x]=='(')find2(x+1,num+1,cnt);
else if(s[x]==')')find2(x+1,num-1,cnt+1);
else
{
mx[x]=')';
find2(x+1,num-1,cnt+1);
if(f==1)return ;
mx[x]='(';
find2(x+1,num+1,cnt);
}
}
int main()
{
cin>>s;
// rep(i,0,250)s+="(*";
memset(dp,0,sizeof(dp));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
l=s.size();
per(i,1,s.size())
{
if(s[i]=='(')b[i]=b[i+1]+1,c[i]=c[i+1];
if(s[i]==')')b[i]=b[i+1],c[i]=c[i+1]+1;
if(s[i]=='*')b[i]=b[i+1],c[i]=c[i+1];
}
b[0]=b[1]+1,c[0]=c[1];
rep(i,0,l)
{
if(i==0)
{
if(s[i]!=')')dp[i][1]=1;
}
else
{
if(s[i]=='(')
{
rep(j,1,i+2)dp[i][j]=dp[i-1][j-1];
}
else if(s[i]==')')
{
rep(j,0,i)dp[i][j]=dp[i-1][j+1];
}
else
{
rep(j,0,i+2)dp[i][j]=dp[i-1][j-1];
rep(j,0,i)dp[i][j]=(dp[i][j]+dp[i-1][j+1])%mod;
}
}
}
cout<<dp[l-1][0]<<endl;
// rep(i,0,s.size())mi+=s[i],mx+=s[i];
mi=mx=s;
if(dp[l-1][0]>0)
{
mi[0]=mx[0]='(';
// cout<<s<<endl;
find1(0,0,0);
f=0;
find2(0,0,0);
cout<<mi<<endl;
cout<<mx<<endl;
}
return 0;
}
此文分享给，和我一样，在做这题时，好奇参考解法是怎样，却苦于找不到资料的有缘人。
版权声明：本文为qq_41856733原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。