POJ 2955 Brackets（区间DP）

快来打我* 2023-06-04 13:57 7阅读 0赞

嗯...

题目链接：http://poj.org/problem?id=2955

一道比较经典的区间dp，注意首先更新dp，然后再转移，转移的时候并没有什么代价，即dp\[i\]\[j\] = max(dp\[i\]\[j\], dp\[i\]\[k\] + dp\[k + 1\]\[j\]

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 #include<cstring>
     4 #include<algorithm>
     5 
     6 using namespace std;
     7 
     8 char s[105];
     9 int dp[1005][1005];
    10 
    11 inline bool judge(int x, int y){
    12     if(s[x] == '(' && s[y] == ')') return 1;
    13     if(s[x] == '[' && s[y] == ']') return 1;
    14     return 0;
    15 }//判断 
    16 
    17 int main(){
    18     while(~scanf("%s", s)){
    19         memset(dp, 0, sizeof(dp));
    20         if(s[0] == 'e') break;
    21         int len = strlen(s);
    22         for(int l = 1; l < len; l++){
    23             for(int i = 0; i < len; i++){
    24                 int j = i + l;
    25                 if(j > len) break;
    26                 if(judge(i, j)){
    27                     if(j - i == 1) dp[i][j] = 2;
    28                     else dp[i][j] = dp[i + 1][j - 1] + 2;
    29                 }//更新dp 
    30                 for(int k = i; k < j; k++){
    31                     dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
    32                 }//转移 
    33             }
    34         }
    35         printf("%d\n", dp[0][len - 1]);
    36     }
    37     return 0;
    38 }

AC代码

转载于:https://www.cnblogs.com/New-ljx/p/11569317.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/6686e828b1344abd90da2fd6c8578da5.png

发表评论取消回复

表情：

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

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

相关阅读

相关 POJ 2955 （区间dp,划分区间求解）

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

Love The Way You Lie/ 2024年02月17日 19:36/ 0 赞/ 42 阅读

相关 [POJ2955]Brackets

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

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

相关 POJ 3280 Cheapest Palindrome（区间DP）

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

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

相关 POJ 2955 Brackets（区间DP）

嗯... 题目链接：http://poj.org/problem?id=2955 一道比较经典的区间dp，注意首先更新dp，然后再转移，转移的时候并没有什

快来打我*/ 2023年06月04日 13:57/ 0 赞/ 8 阅读

相关 Brackets (区间DP)

目录 Brackets (区间DP) 题目题意思路题解 Brackets (区间DP)

绝地灬酷狼/ 2023年06月01日 06:11/ 0 赞/ 5 阅读

相关 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 赞/ 117 阅读

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

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

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

相关 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 赞/ 192 阅读

相关 poj 2253（区间DP）

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

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

相关 POJ1179 Polygon（区间dp）

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

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