poj 2955 【POJ 2955】Brackets（區間DP）－IT工程師數位筆記本

文章出處

入門級區間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 #include #include #include #include #include #include #include #include #include #include #include #include#include #define LL long long#define Pr pair#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-8;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;},int>

就愛閱讀www.92to.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20161116/53956.html

文章列表