【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使用
下一篇 我的文檔
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
