最大符号匹配 动态规划.txt

NUAA ACM OJ源码

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;

//最大符号匹配 动态规划
/*
输入：
([][][)
(])(
((()))
[][][]

输出：
6
2
6
6
*/
#define NMAX 102
int f[NMAX][NMAX];//f[i][j],从第i位到第j位子串的匹配情况
char str[NMAX];//将shuru[]后移一位得道，str[0]不用，方便写转移方程
char shuru[NMAX];

void print(int num)
{	//调试时打印f[][]
	int i,j;
	for(i=1;i<=num;i++) cout<<i<<" ";
	cout<<endl;
	for(i=1;i<=num;i++)
	{
		for(j=1;j<=num;j++)
			cout<<f[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl;
	system("pause");
}
int cal(int num)
{
	int i,j,max,k,m;
	memset(f,0,sizeof(f));
	for(i=1;i<=num;i++) f[i][i]=0;
	for(i=1;i<num;i++)
	{
		if((str[i]=='('&&str[i+1]==')')||(str[i]=='['&&str[i+1]==']'))
			f[i][i+1]=1;
	}
	for(k=3;k<=num;k++)
	{//要枚举的字符串长度
		for(i=1;i<=num-k+1;i++)
		{//要枚举的字符串的起始位置
			j=i+k-1;//结束位置
			max=f[i][j-1];
			if(str[j]==')'||str[j]==']') 
			{	//这种情况才可能增加匹配数
				for(m=i;m<j;m++)
				{//枚举要与末括号匹配的括号位置
					if(m>i)
					{//如果m不是首位，max由三部分组成（1+str[m]之前+str[m]之后的匹配数）
						if((str[m]=='('&&str[j]==')')||(str[m]=='['&&str[j]==']'))
						{
							if(max<1+f[i][m-1]+f[m+1][j-1])
								max=1+f[i][m-1]+f[m+1][j-1];
						}
						else if(max<f[i][m-1]+f[m+1][j-1]) max=f[i][m-1]+f[m+1][j-1];
					}
					else
					{//如果m是首位，max由两部分组成（1+str[m]之后的匹配数）
						if((str[m]=='('&&str[j]==')')||(str[m]=='['&&str[j]==']'))
						{
							if(max<1+f[m+1][j-1])
								max=1+f[m+1][j-1];
						}
						else if(max<f[m+1][j-1]) max=f[m+1][j-1];
					}
				}
			}
			f[i][j]=max;
		}
	}
//	print(num);
	return f[1][num];
}

int main()
{
	int i,num;
	scanf("%s",&shuru);
	while(strcmp(shuru,"end")!=0)
	{
		num=strlen(shuru);
		i=0;
		str[0]='s';
		do
		{
			str[i+1]=shuru[i];
			i++;
		}while(shuru[i-1]!='\0');
		cout<<2*cal(num)<<endl;
		scanf("%s",&shuru);
	}
    return 0;
}