POJ 2955 区间dp

Love The Way You Lie 2022-08-18 11:55 151阅读 0赞

题意：求括号匹配的最大长度

思路：简单区间dp，令dp\[i\]\[j\] 为 区间（i,j）之间的最大匹配长度。

这样dp\[i\]\[j\]  = max( dp\[i\]\[j\] , dp\[i\]\[x\] + dp\[x+1\]\[j\] )  i<x<j

不过dp\[i\]\[j\] 得先初始化，为dp\[i+1\]\[j-1\]  或者 dp\[i+1\]\[j-1\]  +2 ；

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int const maxn = 110;
    char str[maxn];
    int dp[maxn][maxn];
    
    int main()
    {
        while(scanf("%s",str)!=EOF)
        {
            if(str[0]=='e')break;
            int n = strlen(str);
            memset(dp,0,sizeof(dp));
            for(int i = 0 ; i < n ; i++)
            {//初始化
                dp[i][i] = 0 ;
                if((str[i]=='('&&str[i+1]==')')||(str[i]=='['&&str[i+1]==']'))
                    dp[i][i+1] = 2 ;
                else dp[i][i+1] = 0 ;
            }
            for(int k = 2 ; k < n ; k++)
            {
                for(int i = 0 , j = k  ; j < n ; j++ , i++)
                {    //每次i和j相隔k个距离
                    if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']'))   //匹配
                        dp[i][j] = dp[i+1][j-1] + 2 ;
                    for(int x = i ; x < j ; x++)   //区间最值合并
                    {
                        dp[i][j] = max(dp[i][j],dp[i][x] + dp[x+1][j]);
                    }
                }
            }
            printf("%d\n",dp[0][n-1]);
        }
        return 0;
    }
    
    /*
    Auther:LIUYAN
    2015.12.16
    
    ((()))
    ()()()
    ([]])
    )[)(
    ([][][)
    end
    */

发表评论取消回复

表情：

评论列表（有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

相关 [POJ2955]Brackets

题面描述我们给出了正则括号序列的如下归纳定义： · 空序列是正则括号序列 · 如果s是正则方括号序列，那么(s)和\[s\]是正则方括号序列 · 如果a和b

约定不等于承诺〃/ 2023年08月17日 17:38/ 0 赞/ 78 阅读

相关 POJ 3280 Cheapest Palindrome（区间DP）

嗯... 题目链接：http://poj.org/problem?id=3280 这道题首先要清楚：对于构成一个回文串，删去一个字符和加上一个字符是等效的，所以

谁借莪１个温暖的怀抱￠/ 2023年06月04日 13:57/ 0 赞/ 84 阅读

相关 poj（3280）Cheapest Palindrome（区间dp）

题目链接：[http://poj.org/problem?id=3280][http_poj.org_problem_id_3280] 题意：给出一个由m

阳光穿透心脏的1/2处/ 2022年08月26日 15:36/ 0 赞/ 93 阅读

相关 POJ 2955-Brackets（括号匹配-区间DP）

Brackets <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

短命女/ 2022年08月22日 12:30/ 0 赞/ 118 阅读

相关 poj 1141 （区间dp记录路径问题）

题意：括号匹配问题。问需要插入多少个括号是的所有的括号都正好可以匹配。输出其中长度最短的一个。分析：dp\[i\]\[j\] 表示的是在区间(i,j)之间添加的最少的括号数

忘是亡心i/ 2022年08月18日 11:56/ 0 赞/ 111 阅读

相关 POJ 2955 区间dp

题意：求括号匹配的最大长度思路：简单区间dp，令dp\[i\]\[j\] 为区间（i,j）之间的最大匹配长度。这样dp\[i\]\[j\] = max( dp\[i

Love The Way You Lie/ 2022年08月18日 11:55/ 0 赞/ 152 阅读

相关【区间dp】Treats for the Cows POJ - 3186

Think: 1知识点：区间dp 2题意：给定一个长度为n的序列，从1开始取n次，每次可以选取第一个结点或者最后一个结点，每次获取的价值为当前次数乘以选取的结点数值，询

梦里梦外;/ 2022年06月10日 03:51/ 0 赞/ 137 阅读

相关 poj 2253（区间DP）

[原题][Link 1] 思路：求所有路径中最大跳跃距离的最小值，很诡异的是输出答案如果用G++，.3lf%格式会出错，c++可以过 include<cstdio

男娘i/ 2022年06月04日 03:05/ 0 赞/ 183 阅读

相关 POJ1179 Polygon（区间dp）

题意：多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“\”。所有边依次用整数从1到n编号，游戏第1

蔚落/ 2021年11月29日 14:56/ 0 赞/ 287 阅读

相关区间dp

让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小

小鱼儿/ 2021年11月26日 19:50/ 0 赞/ 377 阅读