A - Brackets POJ - 2955 (区间DP模板题)

时间:2021-04-24 04:12:06

题目链接:https://cn.vjudge.net/contest/276243#problem/A

题目大意:给你一个字符串,让你求出字符串的最长匹配子串。

具体思路:三个for循环暴力,对于一个区间i,j,我们先计算出这个区间内合法的有多少个,也就是

if(check(k,j))dp[k][j]=dp[k+][j-]+;

然后就开始求这个区间内的最大值就可以了。

dp[k][j]=max(dp[k][j],dp[k][pos]+dp[pos+][j]);

AC代码:

 #include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
# define ll long long
const int maxn = 2e2+;
const int mod =1e6;
# define LL_inf 0x3f3f3f3f3f3f3f
char str[maxn];
int dp[maxn][maxn];
bool check(int u,int v){
// cout<<str[u]<<" "<<str[v]<<endl;
if((str[u]=='('&&str[v]==')')||(str[u]=='['&&str[v]==']'))return true;
return false;
}
int main(){
while(~scanf("%s",str)){
if(str[]=='e')break;
memset(dp,,sizeof(dp));
int len=strlen(str);
for(int i=;i<len;i++){
for(int j=i,k=;j<len;k++,j++){
if(check(k,j))dp[k][j]=dp[k+][j-]+;
for(int pos=k;pos<j;pos++){
dp[k][j]=max(dp[k][j],dp[k][pos]+dp[pos+][j]);
}
}
}
printf("%d\n",dp[][len-]);
}
return ;
}