【POJ 2955】Brackets(区间DP)
入门级区间DP
问最长的匹配括号长度。只包括()和[]
要求匹配括号不可交叉,即([)]这类不计入
由于不计交叉情况,转移就很直白。
枚举区间长度l,转移为
if( (str[i] == '(' && str[i+l-1] == ')')
|| (str[i] == '[' && str[i+l-1] == ']') )
dp[i][i+l-1] = max(dp[i][i+l-1],dp[i+1][i+l-2]+2);
//合并相邻区间最长括号匹配数
for(int j = i; j < i+l; ++j)
dp[i][i+l-1] = max(dp[i][i+l-1],dp[i][j]+dp[j+1][i+l-1]);
代码以下:
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <climits>
#include <ctime>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread(ch) freopen(ch,"r",stdin)
#define fwrite(ch) freopen(ch,"w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const int mod = 1e9+7;
const double eps = 1e⑻;
char str[233];
int dp[233][233];
bool cal(int i,int j)
{
return (str[i] == '(' && str[j] == ')') || (str[i] == '[' && str[j] == ']');
}
int main()
{
//fread("");
//fwrite("");
while(~scanf("%s",str) && str[0] != 'e')
{
int len = strlen(str);
memset(dp,0,sizeof(dp));
for(int l = 2; l <= len; l++)
{
for(int i = 0; i+l <= len; ++i)
{
if(cal(i,i+l-1)) dp[i][i+l-1] = max(dp[i][i+l-1],dp[i+1][i+l-2]+2);
for(int j = i; j < i+l; ++j)
dp[i][i+l-1] = max(dp[i][i+l-1],dp[i][j]+dp[j+1][i+l-1]);
}
}
printf("%d\n",dp[0][len-1]);
}
return 0;
}
上一篇 java加解密之RSA使用
下一篇 我的文档