poj 2955 Brackets 括号匹配 区间dp
2024-08-28 15:01:59
题意:最多有多少括号匹配
思路:区间dp,模板dp,区间合并。
对于a[j]来说:
刚開始的时候,转移方程为dp[i][j]=max(dp[i][j-1],dp[i][k-1]+dp[k][j-1]+2), a[k]与a[j] 匹配,结果一组数据出错
([]])
检查的时候发现dp[2][3]==2,对,dp[2][4]=4,错了,简单模拟了一下发现,dp[2][4]=dp[2][1]+dp[2][3]+2==4,错了
此时2与4已经匹配,2与3已经无法再匹配。
故转移方程改为dp[i][j]=max(dp[i][j-1],dp[i][k-1]+dp[k+1][j-1]+2)。a[k]放弃使用,幸运的一次ac
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
char a[110];
int dp[110][110];
int main()
{
while(scanf("%s",a+1)!=EOF)
{
int lena=strlen(a+1);
int i,j,k;
if(lena==3&&a[1]=='e'&&a[2]=='n'&&a[3]=='d')
{
break;
}
//cout<<"lena== "<<lena<<endl;
memset(dp,0,sizeof(dp));
for(i=lena-1;i>=1;i--)
{
for(j=i+1;j<=lena;j++)
{
dp[i][j]=dp[i][j-1];
for(k=i;k<=j-1;k++)
{
if((a[k]=='('&&a[j]==')')||(a[k]=='['&&a[j]==']'))
{
dp[i][j]=max(dp[i][k-1]+dp[k+1][j-1]+2,dp[i][j]);
}
}
//cout<<"i== "<<i<<" j== "<<j<<" dp[i][j]== "<<dp[i][j]<<endl;
}
}
cout<<dp[1][lena]<<endl;
}
return 0;
}
最新文章
- 【intellij idea】Project Structure 讲解
- jquery validate 自定义验证方法
- Python Import 详解
- 支持多选的Spinner控件
- while, do-while ,switch&#183;&#183;&#183;case语句的学习与运用
- ios开发之触摸&;手势识别
- excel多个文件合并
- C++ 常见问题
- 【迪杰斯特拉双关键字最短路】【HDU3790】【最短路径问题】
- jsp获取枚举的值
- zookeeper错误KeeperErrorCode = ConnectionLoss解决
- java做单用户的多重并发会话数限制
- 通过案例了解Hystrix的各种基本使用方式
- BZOJ4942 NOI2017整数(线段树)
- linux内核中的dquot是什么?
- spring colud 博客
- HIVE表保存的路径
- Mongo.exe 无法定位程序输入点terminate于动态链接库 *.dll的解决办法
- SQL Serever学习5——数据库配置
- C/C++程序内存情况
热门文章
- 使用Ant打包Android应用具体解释——Ant使用解析
- mahout的特性(三)
- Catch Me If You ... Can&#39;t Do Otherwise--转载
- 淘宝分类导航条;纯css实现固定导航栏
- python-string中部分string替换
- git在本地分支上 git pull远程分支时,状况
- ThinkPHP5.0---URL访问
- FansMail:邮件发送标准API与技术实现(Java)
- 洛谷 P2069 松鼠吃果子
- UVA 10125 - Sumsets(POJ 2549) hash