括号匹配(二)
时间限制:1000 ms | 内存限制:65535 KB
难度:6
如:
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的
每组测试数据都只有一行,是一个字符串S,S中只包含以上所说的四种字符,S的长度不超过100
4 [] ([])[] ((] ([)]
0 0 3 2
思路:
区间 DP。设 dp [ i ] [ j ] 表示从 i 到 j 使其匹配成功的最小添加数量。所以:
1.dp [ i ] [ j ] = min ( dp [ i ] [ j ] , dp [ i ] [ i + k ] + dp [ k + 1 ] [ j ] ) ( i <= k < j);
2.若 s [ i ] 与 s [ j ] 是彼此匹配的括号时,还需要比较 dp [ i ] [ j ] = min ( dp [ i ] [ j ] ,dp [ i + 1] [ j - 1] )。
初始化的时候,当 i == j 时,即为本身时,dp [ i ] [ j ] = 1;要求最小值,则当 i < j 时,dp [ i ] [ j ] = INF;当 i > j 时,dp [ i ] [ j ] = 0,这是需要注意的。
比如当这个括号串为 “()”时,第一条 dp 公式更新到 dp [ 0 ][ 1 ] = 2,若把全部的值都初始化为 INF 的话,根据第二条 dp 更新公式,却得不到 0 的结果,因为 dp [ 1 ] [ 0 ] = INF,所以当 i > j 时,应该初始化 dp [ i ] [ j ] = 0 。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int INF = 99999999; int dp[105][105]; int main() { int n; scanf("%d", &n); while (n--) { char s[105]; int len; scanf("%s", s); len = strlen(s); for (int i = 0; i < len; ++i) for (int j = 0; j < len; ++j) { if (i < j) dp[i][j] = INF; if (i > j) dp[i][j] = 0; if (i == j) dp[i][j] = 1; } for (int j = 1; j < len; ++j) { for (int i = j - 1; i >= 0; --i) { for (int k = i; k < j; ++k) { dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]); } if (s[i] == '(' && s[j] == ')') dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]); if (s[i] == '[' && s[j] == ']') dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]); } } printf("%d\n", dp[0][len - 1]); } return 0; }
相关推荐
区间DP概率DP树形DP插头DP,每种DP一道典型例题,有助于初学者
区间dp课程ppt。内容包含石头合并1、2,删除字符串、最大回文数、能量项链、乘积最大问题,等区间dp重要内容。
题目分析:最优性问题,且是对区间操作的,而且数据范围满足 n^3 的时间复杂度,综上可以考虑区间dp,因为题目已经明确了需要求什么,所以我们不妨设 dp[ i ][ j ] 为区间 [ i , j ] 合并后的最短数列的长度,因为...
区间DP是一类在区间上进行动态规划的最优问题,一般是根据问题设出一个表示状态的dp,可以是二维的也可以是三维的,一般情况下为二维。然后将问题划分成两个子问题,也
算法-动态规划- 区间 DP(包含源程序).rar
1. 基本区间DP#include <bits/stdc++.h>using namespace std;
算法-动态规划- 区间 DP- 石子合并三讲(包含源程序).rar
这是一种立体匹配算法,可以进行快速匹配。
SAD+DP算法,是在双目立体视觉中,求左右图对匹配深度图
得宝 迪普乐DP-F850 DP-F650 DP-F620 DP-F550 DP-F520 制版印刷一体机 维修手册
蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A2DP最新协议版本,A2DP_v1.3.2.pdf;蓝牙A...
DP83848中文数据手册 DP83848中文文档 全篇翻译无排版 DP83848C / I / VYB / YB PHYTER™QFP单端口10/100 Mb / s以太网物理层收发器 从–40°C到105°C的多个温度范围•IEEE 802.3 ENDEC,10BASE-T收发器和 • 低...
动态优化处理立体匹配问题,展示了下效果,简单实现
1. 同一项目中S7-1200 与 S7-300 集成 DP 口之间 DP 主从通信,S7-1200 通过CM1243-5作为 DP 主站,S7-300 集成 DP 口作为 DP 从站; 2. 不同项目中S7-1200 与 S7-300 集成 DP 口之间 DP 主从通信,S7-1200 通过CM...
DP接口介绍 1、 DP接口简介 2、 DP接口分类 2.1 标准DP接口 2.2 Mini-DP接口 3、 DP版本迭代 3.1 DP 1.0版本 3.2 DP 1.1a版本 3.3 DP 1.2版本 3.4 DP 1.3版本 3.5 DP 1.4版本 3.6 DP 2.0版本 3.7 版本对比 4、 DP...
VESA官网的DP1.4标准协议
用于仿真KDP二型晶体的响应特性,需要mathmatica9.0以上版本
Android 蓝牙 A2dp 听歌卡音?audio数据到a2dp通道流程解析----A2dp流控原理(Acl Flow Control),一文搞懂蓝牙卡音问题处理
采药问题的二维DP解法