From Google Earth
题目大意是说，对于一个给定的括号序列\(S\)，找出其最长的子序列，该子序列应该是括号匹配的，输出其长度。
大概是最基础的区间dp了。
\(dp[i][j]\)表示的是在区间\([i,j]\)内，最长的满足要求的子序列的长度。如果\(S_i\)与\(S_j\)配对，则有 \[ dp[i][j]=max(dp[i][j],dp[i+1][j-1]+2) \] 但这样得到的\(dp[i][j]\)并不一定是最大的。以第二个样例为例：
对于区间\([1,6]\)，\(S_1\)和\(S_6\)是配对的，所以有\(dp[1][6]=max(dp[1][6],dp[2][5]+2)\)，而\(dp[2][5]\)为2，如果只是从\(dp[2][5]+2\)转移过来，就会忽略掉\(S_1S_2\)以及\(S_5S_6\)这两对配对括号。故我们还需要枚举区间\([i,j]\)内的断点\(k\)，从\(dp[i][k]+dp[k+1][j]\)转移得到\(dp[i][j]\)。
代码如下:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#include <assert.h>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dp[105][105];
char str[105];
bool check(char ca,char cb)
{
if((ca=='('&&cb==')')||(ca=='['&&cb==']')) return 1;
return 0;
}
int main()
{
while(scanf("%s",str+1)!=EOF){
if(str[1]=='e') break;
mst(dp,0);
int len=strlen(str+1);
for(int i=1;i<=len;i++)
dp[i][i]=0;
for(int i=len-1;i>=1;i--){
for(int j=i+1;j<=len;j++){
if(check(str[i],str[j])){
dp[i][j]=max(dp[i][j],dp[i+1][j-1]+2);
}
for(int k=i;k<j;k++)
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
printf("%d\n",dp[1][len]);
}
return 0;
}