poj1141&timus1183 Brackets Sequence

题目

http://poj.org/problem?id=1141

题意

给出一个由字符‘(‘, ‘)‘, ‘[‘, 和‘]‘构成的字符串. 找出一个最短的合法字符串，使得给出的字符串是这个字符串的子序列。

思路

数据范围100 可以\(O(n^3)\) 考虑区间DP
f(i,j)表示这个串在[i,j]区间内最少添加几个括号才能把这个串变成括号序列。
1.\(f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);\) 枚举k
2.当这个区间最外围的两个括号匹配时直接取里面的值. 如:( []){}} )
然后递归输出答案

注意

有时会出现一些奇奇怪怪的RE现象 原因可能如下
1.要用scanf printf
2.要用char 而不是 string
3.把strlen提前一个变量里 不要每次都求
4.f初始值inf
5.更新f的顺序

代码

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<stack>
using namespace std;
#define _ 0
const int maxn=105;
const int inf=1e9;
int f[maxn][maxn];
char s[maxn];
void print(int l,int r)
{
	if(l>r)
		return ;
	if(l==r)
	{
		if(s[l]==‘(‘||s[l]==‘)‘)
			printf("()");
		else
			printf("[]");
		return ;
	}
	if(f[l][r]==f[l+1][r-1]&&((s[l]==‘(‘&&s[r]==‘)‘)||(s[l]==‘[‘&&s[r]==‘]‘)))
	{
		printf("%c",s[l]);
		print(l+1,r-1);
		printf("%c",s[r]);
		return ;
	}
	for(int k=l;k<r;k++)
	{
		if(f[l][r]==f[l][k]+f[k+1][r])
		{
			print(l,k);
			print(k+1,r);
			return ;
		}
	}
}
int main(){
//    ios::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%s",s);
    for(int i=0;i<=strlen(s)-1;i++)
    	f[i][i]=1;
    for(int l=1;l<=strlen(s)-1;l++)
    {
	    for(int i=0;i<=strlen(s)-1-l;i++)
	    {
    		int j=i+l;
    		f[i][j]=inf; 
    		if((s[i]==‘(‘&&s[j]==‘)‘)||(s[i]==‘[‘&&s[j]==‘]‘))
    			f[i][j]=f[i+1][j-1];
    		for(int k=i;k<=j-1;k++)
    			f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
		}
	}
	print(0,strlen(s)-1);
	printf("\n");
	return ~~(0^_^0);
}

poj1141&timus1183 Brackets Sequence

原文：https://www.cnblogs.com/a-little-mushroomspy/p/14614795.html