經過這個題目的考察發現自己還是很菜的。這個題目就是說現在給你一些括號，然後問這些括號的最大匹配長度是多少。這個題目其實和矩陣合並的那個思路差不多，dp[i][j]是從i到j的最大匹配，注釋在程序裡面，具體看程序。寫的比較差，哎。
[cpp]
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<string>
#include<cstring>
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<len;i++)
{//初始化從i到i+1這個的dp
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<k;g++)
dp[j][k]=maxi(dp[j][k],dp[j][j+g]+dp[j+g+1][k]);
}
cout<<dp[1][len]*2<<endl;
}
return 0;
}
</SPAN>
#include<iostream>
#include<string>
#include<cstring>
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<len;i++)
{//初始化從i到i+1這個的dp
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<k;g++)
dp[j][k]=maxi(dp[j][k],dp[j][j+g]+dp[j+g+1][k]);
}
cout<<dp[1][len]*2<<endl;
}
return 0;
}
