Feng003

DP

codeforces(2) 图论(2) 基础数据结构(2) 字符串(1) 数据结构课程(1) 概率期望(1) 算法课课程作业(4) 题解(6)

/ 注册

全部文章 / DP （共3篇）

DP入门

动态规划算法（DP,Dynamic Programming）它针对满足特定条件的一类问题，对各状态维度进行分阶段、有顺序、无重复、决策性的遍历求解。阶段动态规划算法把原问题视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个阶段。在完成前一个阶段的计算后，动态规划才会执行下一阶段的计...

DP

2021-01-26

0 744

Array Without Local Maximums（codeforces1068D）计数类DP

题意：给你一个长度为n的数组a,（1<=n<=1e5 ,1<=a[i]<=200 or a[i]=-1）。a[i]=-1代表i这个位置的数是未知的否则已知，对于每个未知的数你可以把它设置成1-200之间的任意整数。问你有几种设置方法可以使得整个序列满足：a[1]<=a[...

计数类dp DP

2020-04-19

0 566

Coloring Brackets CodeForces - 149D （区间dp）

问题：给你一个长度为n的合法括号序列，你要对每一对括号的其中一个半括号（必须并且只能为一个）染色，有两种颜色可以选择。要求染完色后，序列里不存在相邻的位置是同种颜色的（两个都未染色的算合法）。求一共有几种染色方案。答案取模1e9+7。思路: 区间dp。记dp[l][r][i][j]为对区间[l,r...

括号匹配区间dp

2020-04-12

0 544