间隔DP基础 POJ2955——Brackets

间隔DP基础 POJ2955——Brackets

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

取血怒。first blood,第一区间DP,这样第一次没有以某种方式在不知不觉中下降~~~


题目尽管是鸟语。但还是非常赤裸裸的告诉我们要求最大的括号匹配数。DP走起~

dp[i][j]表示区间[i,j]的最大匹配数。那么最重要的状态转移方程就是:

dp[i][j]=max(dp[i][k]+dp[k+1][j])

对啦,要先初始化边界啊。两步走~:

memset(dp,0,sizeof dp);

if str[i]==str[i+1]   则:dp[i][i+1]=2       请看—->> 该字符串 ( [ ] [ ] [ )  非常好懂有木有



万恶的贴代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[110][110];
char s[110];
bool check(int i,int j)//推断是不是匹配的
{
    if(s[i]=='['&&s[j]==']') return true;
    if(s[i]=='('&&s[j]==')') return true;
    return false;
}
int main()
{
    while(scanf("%s",s)!=EOF){
        if(strcmp(s,"end")==0) break;
        int l=strlen(s);
        memset(dp,0,sizeof dp);
        for(int i=0;i<l;i++){                             //初始化
            if(check(i,i+1)){
                dp[i][i+1]=2;
            }
        }

        for(int p=3;p<=l;p++){                       //枚举区间长度
            for(int i=0;i<=l-p;i++){                //枚举区间起点
                int j=i+p-1;
                if(check(i,j)){
                    dp[i][j]=dp[i+1][j-1]+2;
                }
                for(int k=i;k<j;k++){           //将区间分成两段
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]);
                }
            }
        }
        cout<<dp[0][l-1]<<endl;
    }
    return 0;
}


       

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116728.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • ngx-echarts的使用

    ngx-echarts的使用

  • 铁通宽带dns地址(成都dns的服务器地址是多少)

    全国各地电信DNS见下:—————————————————————-北京DNS地址:202.96.199.133202.96.0.133202.106.0.20202.106.148.1202.97.16.195上海DNS地址:202.96.199.132202.96.199.133202.96.20

  • 一些常用单位之间的换算

    一些常用单位之间的换算一些常用单位之间的换算单位表格汇总单位表格汇总请注意下方的表格:目前只对链接(也就是文字颜色有变换的那个)产生了单位的换算,其他的没有做换算,如果有清楚的可以在本篇博文下留言,正确的留言单位换算就打算加上链接,错误的就请大家帮忙纠正一下,感谢各位配合!!!常用物理量的名称、符号和单位名称…

  • mysql8分区表_MySQL 分区表[通俗易懂]

    mysql8分区表_MySQL 分区表[通俗易懂]MySQL分区就是将一个表分解为多个更小的表。从逻辑上讲,只有一个表或一个索引,但在物理上这个表或者索引可能由多个物理分区组成。每个分区在物理上都是独立的。MySQL数据库分区类型:Range分区:行数据基于属于一个给定连续区间的列值放入分区。List分区:和Range分区类似,只是List分区面向的是离散的值。Hash分区:根据用户自定义的表达式的返回值来进行分区,返回值不能为负数。Key分区:…

  • jetbrains 免费激活码 2022【最新永久激活】

    (jetbrains 免费激活码 2022)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

  • Codelf 命名神器

    Codelf 命名神器对于刚入职的新手开发小白,英语水平不好的可以使用下面这款变量命名神器地址:https://unbug.github.io/codelf/

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号