间隔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)


相关推荐

  • 用python做qq聊天机器人_python完整项目

    用python做qq聊天机器人_python完整项目是否也像拥有自己的机器人呢?不挨个展示了。比如说你想实现一个夸人的功能:”””作者:川川时间:2021/4/6″””fromnonebot.adapters.cqhttpimportMessage,PokeNotifyEvent,Botfromnonebotimporton_noticeimportwarningsfromnonebot.permissionimport*importrequestswarnings.filterwarnings(“i

  • html空格代码&nbsp_html中的转义字符

    html空格代码&nbsp_html中的转义字符一般只要没有打错你那应该用了flex布局flex会影响一些语法而且也会导致空格符实习失效而且如果你设置了white-space:nowrap;overflow:hidden;text-overflow:ellipsis;会发现超出部分会隐藏但并不会出现省略号flex还是会影响一些基础样式的慎用…

  • django验证码登录_双重认证怎么关闭

    django验证码登录_双重认证怎么关闭djoser是什么?作用:Django认证系统的REST实现。djoser库提供了一组DjangoRestFramework视图,用于处理注册、登录、注销、密码重置和帐户激活等基本操作。它适用于

  • php工厂模式详解

    php工厂模式详解工厂类就是一个专门用来创建其它对象的类,工厂类在多态性编程实践中是非常重要的。它允许动态替换类,修改配置,会使应用程序更加灵活。掌握工厂模式对Web开发是必不可少的。工厂模式通常用来返回类似接口的不同的类,工厂的一种常见用法就是创建多态的提供者。通常工厂模式有一个关键的构造,即一般被命名为factory的静态方法。这个静态方法可以接受任意数量的参数,并且必须返回一个对象。P

  • Mysql怎样控制replace替换的次数?

    Mysql怎样控制replace替换的次数?

    2021年10月21日
  • 1.3万亿条数据查询如何做到毫秒级响应?

    1.3万亿条数据查询如何做到毫秒级响应?

    2020年11月14日

发表回复

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

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