【算法】bracket-sequence(DFS、DP)

港控/mmm° 2022-08-28 01:46 195阅读 0赞

给定一个长度为 n 的括号序列 S，其中有些位置上的字符缺失被换为 ∗，询问存在多少种将 S 中的 ∗ 替换为 ( 或 ) 的方案，使得 S仍然合法。若存在方案，输出字典序最小和最大的方案。

对于一个括号序列 A 而言，合法的定义为：

1.  ‘A = ()’ 是合法的
2.  如果存在一个合法的 B，使得 ‘A = (B)’ ，则 A 是合法的
3.  如果存在合法的 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
    //(()*)***)))**) 该输出有误！

## 二、提交的动态规划方法 ##