POJ - 2955 Brackets （区间DP）

传送门：POJ - 2955

思路分析

定义dp数组dp[i][j]为区间i-j之间的最大匹配数量，如果第i个括号和第j个括号匹配的话，很容易想到状态转移方程为dp[i][j]=dp[i+1][j-1]+2,然后再枚举i到j之间的括号k，更新最大值为，dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j])。

样例输入

((()))
()()()
([]])
)[)(
([][][)
end

样例输出

6
6
4
0
6

AC代码

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

const int INF = 0x3f3f3f3f;

int dp[1111][1111];
string s;

int judge(int l,int r){
    if((s[l]=='['&&s[r]==']')||(s[l]=='('&&s[r]==')'))
        return 1;
    else
        return 0;
}

int main() {
    IOS;
    while(cin>>s){
        if(s=="end")
            break;
        int n=s.size();
        memset(dp,0,sizeof dp);
        for(int i=1;i<n;i++){
            for(int l=0,r=l+i;r<n;l++,r++){
                if(judge(l,r))
                    dp[l][r]=dp[l+1][r-1]+2;
                for(int k=l;k<r;k++)
                    dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]);
            }
        }
        cout<<dp[0][n-1]<<endl;
    }
    
    return 0;
}