UVA 1626 括号序列（区间dp）

Myth丶恋晨 2024-02-17 19:36 78阅读 0赞

分析：区间dp，装填方程：dp(i,j)=min(dp(i,k)+dp(k+1,j)) 其中（i<=k<j） dp(i,j)表示从第i个字符到第j个字符的最小需要添加括号字符的个数，最后递归打印出字符即可。

不知道为什么voj上用gets读取字符串会编译错误，改成fgets就对了。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<string>
    #include<algorithm>
    using namespace std;
    const int maxn=100+10;
    int dp[maxn][maxn];
    char s[maxn];
    bool match(int i,int j){
    	if(s[i]=='(' && s[j]==')')return true;
    	if(s[i]=='[' && s[j]==']')return true;
    	return false ; 
    }
    
    void print(int i,int j){
    	if(i>j)return ;
    	if(i==j){
    		if(s[i]=='(' || s[i]==')')printf("()");
    		else if(s[i]=='[' || s[j]==']')printf("[]");
    		return ;
    	}
    	
    	if(dp[i][j]==dp[i+1][j-1] && match(i,j)){
    		printf("%c",s[i]);
    		print(i+1,j-1);
    		printf("%c",s[j]);
    		return ;
    	}
    	
    	for(int k=i;k<j;k++){
    		if(dp[i][j]==dp[i][k]+dp[k+1][j]){
    			print(i,k);
    			print(k+1,j);
    			break;
    		}
    	}
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	getchar();  //吃掉换行
    	while(T--){
    		getchar();  //吃掉换行
    	    //gets(s+1);
    	    fgets(s+1,maxn,stdin);
    		int l=strlen(s+1);
    	memset(dp,0,sizeof(dp));
    	for(int i=1;i<=l;i++)
    	 dp[i][i]=1;
    	 
    	 for(int len=2;len<=l;len++)   //长度 
    	  for(int i=1;i<=l-len+1;i++){   //起点 
    	  	int j=i+len-1;   //终点 
    	  	dp[i][j]=maxn;
    	  	if(match(i,j))dp[i][j]=dp[i+1][j-1];
    	  	else dp[i][j]=dp[i][j-1]+1;
    	  	
    	  	for(int k=i;k<j;k++)
    	  	dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
    	  }
    	  
    	  print(1,l);
    	  printf("\n");
    	  if(T)printf("\n");
    //	  printf("%d\n",dp[1][l]);
    	}
    	return 0;
    }