区间dp
作者：
asukaqaqzz
,
2022-02-21 12:20:37
,
所有人可见
,
阅读 357
区间动态规划不同题目之间主要是靠区间合并来划分的，区间dp一共有两种区间合并的方式
- 两点式的区间合并
- 两个大区间，枚举中断点的区间合并
区间合并:两点
| 题目 |
题意 |
思路/关键字 |
题解 |
| 小a的回文串 |
求环形的最大子串 |
环形,子串,模板 |
题解 |
| 1222.密码脱落 |
求最长回文子序列 |
模板题 |
题解 |
| 1489.田忌赛马 |
赢200,输-200,平局0,求max |
区间dp,逆向思维,判断条件 |
题解 |
| 合并回文子串 |
按顺序从两个字符串中选,求最大回文子串 |
回文子串 |
题解 |
| P3205 [HNOI2010]合唱队 |
给定目标序列,求是多少个初始序列转换 |
状态机,判断条件 |
题解 |
| P1220.关路灯 |
n个路灯,每分钟消耗功率,求最小能量 |
状态机,左右端点,前缀和优化 |
题解 |
区间合并:中断点
| 题目 |
题意 |
思路/关键字 |
题解 |
| 石子合并 |
一列的石子,每次合并相邻两个 |
模板题 |
题解 |
| cf607B |
每次消除最长回文子串,求最小消除次数 |
区间dp,枚举元区间发现规律 |
题解 |
| USACO16OPEN 248G |
每次合并相邻两个,求合并后最大数字 |
石子合并的拓展题 |
题解 |
| 1068.环形石子合并 |
石子被摆放成一个环,求每次合并相邻石子所获得的max,min |
环形!!!注意 |
题解 |
| 479.加分二叉树 |
已知中序遍历1~n,每个结点有分数,构造子树求最大加分 |
枚举中断点,分割区间,树 |
题解 |
| 1069.凸多边形的划分 |
有一个凸多边形,每个点上都有对应的分数,求划分成n-2个三角形且分数乘积最小 |
高精度，划分独立子集/区间 |
题解 |
| 321.棋盘分割 |
8x8的棋盘,分割成k个,求最小方差 |
二维区间dp,记忆化搜索,精度 |
题解 |
区间合并:两者结合
