题目：Brackets
题意：
求字符串s的满足完全匹配的最长子串
分析：
dp[i][j]表示区间[i,j]内的最长匹配 状态转移： 1.dp[i][j] = dp[i][j-1] //即第 j 个括号不能匹配 2.考虑第 j 个括号可以匹配的情况 在区间[i,j-1]中找到一个k满足s[k]可以和s[j]匹配 dp[i][j] = max(dp[i][j],dp[i][k-1]+2+dp[k+1][j-1]) 这里的2是把s[k]和s[j]加入匹配串
代码：
#define mem(a,x) memset(a,x,sizeof(a)) #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; /* dp[i][j]表示区间[i,j]内的最长匹配 状态转移： 1.dp[i][j] = dp[i][j-1] //即第 j 个括号不能匹配 2.考虑第 j 个括号可以匹配的情况 在区间[i,j-1]中找到一个k满足s[k]可以和s[j]匹配 dp[i][j] = max(dp[i][j],dp[i][k-1]+2+dp[k+1][j-1]) 这里的2是把s[k]和s[j]加入匹配串 */ int dp[111][111]; char s[111]; bool match(char a,char b) { return (a=='('&&b==')')||(a=='['&&b==']'); } int DP(int i,int j) { if (i >= j) return 0;//显然dp[i][i]一个字符无法匹配 if (~dp[i][j]) return dp[i][j]; dp[i][j] = DP(i,j-1); for (int k = i;k <= j-1;++k) { if (match(s[k],s[j]))//k < j { dp[i][j] = max(dp[i][j],DP(i,k-1)+2+DP(k+1,j-1)); } } return dp[i][j]; } int main() { while (~scanf("%s",s)) { if (strcmp(s,"end") == 0) break; mem(dp,-1); int len = strlen(s) - 1; Pintc(DP(0,len),'\n'); } return 0; }