经过这个题目的考察发现自己还是很菜的。这个题目就是说现在给你一些括号，然后问这些括号的最大匹配长度是多少。这个题目其实和矩阵合并的那个思路差不多，dp[i][j]是从i到j的最大匹配，注释在程序里面，具体看程序。写的比较差，哎。
[cpp]
#include
#include
#include
using namespace std;
int dp[205][205];//表示从i到j的最大匹配。
string str;
//写个函数判断这两个位置是不是匹配的。
bool match(int i,int j)
{
if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']'))
return true;
else return false;
}
int maxi(int a,int b)
{
if(a>b)
return a;
else return b;
}
int main()
{
int i,j,k,len,g;
while(cin>>str)
{
if(str[0]=='e'&&str[1]=='n'&&str[2]=='d')
break;
memset(dp,0,sizeof(dp));
len=str.size();
for(i=1;i
if(match(i-1,i)==true)
dp[i][i+1]=1;
}
for(i=3;i<=len;i++)
for(j=1;j<=len-i+1;j++)
{
k=j+i-1;
//这一步是必须得，这个相当于是最后一个和第一个匹配，然后找中间的最大匹配
//这个状态下面的for覆盖不了，必须单独判断一下
if(match(j-1,k-1)==true)
dp[j][k]=dp[j+1][k-1]+1;
//这个相当于是从j开始找到一个位置的最大匹配加上从这个位置到k的最大匹配
//有点分治法的味道。
for(g=0;g
}
cout<
return 0;
}
#include
#include
#include
using namespace std;
int dp[205][205];//表示从i到j的最大匹配。
string str;
//写个函数判断这两个位置是不是匹配的。
bool match(int i,int j)
{
if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']'))
return true;
else return false;
}
int maxi(int a,int b)
{
if(a>b)
return a;
else return b;
}
int main()
{
int i,j,k,len,g;
while(cin>>str)
{
if(str[0]=='e'&&str[1]=='n'&&str[2]=='d')
break;
memset(dp,0,sizeof(dp));
len=str.size();
for(i=1;i
if(match(i-1,i)==true)
dp[i][i+1]=1;
}
for(i=3;i<=len;i++)
for(j=1;j<=len-i+1;j++)
{
k=j+i-1;
//这一步是必须得，这个相当于是最后一个和第一个匹配，然后找中间的最大匹配
//这个状态下面的for覆盖不了，必须单独判断一下
if(match(j-1,k-1)==true)
dp[j][k]=dp[j+1][k-1]+1;
//这个相当于是从j开始找到一个位置的最大匹配加上从这个位置到k的最大匹配
//有点分治法的味道。
for(g=0;g
}
cout<
return 0;
}