Mrhanice

区间DP

codeforces(2) DP基础(3) POJ(8) UVA(14) 云服务器(1) 图论(2) 扩展欧几里得(1) 杂谈(2) 树状数组(1) 状态压缩DP(1) 状态空间搜索(1) 简单水题(3) 线段树(4) 背包问题(3)

/ 注册

全部文章 / 区间DP （共4篇）

Coloring Brackets CodeForces - 149D

区间DP 题目描述：输入一串保证合法的括号序列，要求给这个括号序列串染色，满足三个要求：（1·）染色要不为红，要么为蓝，要么不染色（2）每队匹配的括号，只能有一个染色（3）相邻的染色的括号不能染一个颜色。解题分析：定义dp[l][r][x][y]为左边界为l，染色为x,右边界为r，...

2017-11-24

0 768

POJ 1651 Multiplication Puzzle

题目描述：给你n个数，拿走一个数，会获得一个值，该值是这个数*它左边的数*它右边的数，最后的结果是取走中间n-2个数所获得的值的和。因为选取的顺序不一样，所获得的值也不一样，求取走中间n-2个值，最小的结果。解题分析：其实就是类似矩阵连乘的思想，矩阵连乘中选取k作为最后一次乘法的中间矩阵，...

2017-10-13

0 583

Brackets sequence UVA - 1626

区间DP 题目描述：输出最短的满足括号匹配的字符串，该字符串满足，输入时该字符串的子串。解题分析：先做的POJ 2955-Brackets，两道题虽然不一样，但是该题的想法可以应用到本题上，定义dp[i][j]为以第i个字符开头，以第j个字符结尾的，最长匹配子串的长度。因为对于输入...

2017-10-11

0 492

POJ 2955-Brackets

区间 DP 题目描述：求一个字符串的最长括号匹配子串（非连续）解题分析：状态转移方程全在题目里，定义了两种括号匹配的子串： 1若s是匹配的字符串，则（s）,[s]也是，那么状态转移方程是if(s[i] == '(' && s[j] ==')' || s[i]...

2017-10-11

0 496