POJ2955 (括号匹配)[区间DP]

发表于 | 更新于 | | 阅读次数：

这题是区间DP，状态转移方程d[l][r]=d[l-1][r-1]+2, s[l]与s[r]可以匹配, d[l][r]=max{d[l][k-1]+d[k][r]}, l<k<=r

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=109;
int dp[maxn][maxn];
char s[maxn];
bool match(char a,char b) {
    if(a=='(' && b==')') return true;
    if(a=='[' && b==']') return true;
    return false;
}
int main() {
    while(~scanf("%s",s)) {
        if(strcmp(s,"end")==0) break;
        int n=strlen(s);
        memset(dp,0,sizeof(dp));
        for(int len=2;len<=n;len++) {
            for(int l=1;l+len-1<=n;l++) {
                int r=l+len-1;
                if(match(s[l-1],s[r-1])) dp[l][r]=dp[l+1][r-1]+2;
                for(int k=l+1;k<=r;k++)
                    dp[l][r]=max(dp[l][r],dp[l][k-1]+dp[k][r]);
            }
        }
        printf("%d\n",dp[1][n]);
    }
}