秃头小白

区间dp

01背包(1) bfs(4) dfs(6) dfs序讲解(1) Dijkstra算法优先队列优化(2) dp(7) KMP(1) LCA(4) STL(1) 二分(5) 二分图(3) 二进制(1) 二进制枚举(3) 优先队列(1) 倍增(2) 分治(2) 前缀和与差分(3) 博弈论(1) 图(1) 并查集(5) 快速幂(1) 思维题(55) 数学题(7) 数论(2) 整除分块（数论）(1) 最小生成树(2) 有关约数（质因数等）的基础数论(2) 栈(1) 树吧(5) 树状dp(1) 树状数组(2) 树状数组+dfs序(2) 模拟(4) 滑动窗口(4) 状压dp(1) 离散化+并查集(1) 离散化讲解及入门例题(2) 签到题(2) 素数筛(1) 线段树(10) 贪心(12) 逆元(1) 逆序对的三种求法(1) 题解(16) 高精度(8)

/ 注册

全部文章 / 区间dp （共11篇）

Tian Ji -- The Horse Racing

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1052 解题思路雨巨讲的思路：区间dp。记田忌为a，齐王为b。将两人的马从大到小排序。dp[i][j]表示a的从i到j匹马，与b的从n-j+i匹马到n匹马比赛的净胜数。judge(i,j)表示的是判断a...

2020-12-06

0 615

能量项链来自专栏

博客破百祭！！！题目链接 https://www.luogu.com.cn/problem/P1063 解题思路一道十分类似的题成环已经不是难点了吧，化环为链。与上面那个题不同的是这个题两个数也可以操作，因为是俩珠子，形如珠子1(10,2) 珠子2(10,2)，最大的得分为10*2*10=20...

2020-10-16

2 626

Multiplication Puzzle 来自专栏

题目链接 http://poj.org/problem?id=1651 解题思路比较简单，就是板子题稍微改了改转移方程。每次这种题，如果你想不出[i,k]和[k+1,j]与[i,j]的关系，你就想你要枚举的k的意义是什么，确定了k的意义之后就方便建立转移方程了。比如这个题，首先可以确定的是dp[i...

2020-10-16

0 608

You Are the One

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=4283 解题思路 dp[i][j]表示假如只有j-i+1个人，分别为i，i+1，……，j，这j-i+1个人进入小黑屋的愤怒值之和。对于区间[i,j]，每次只考虑第i个人的位置，那么他上场的顺序为第1个~第...

2020-10-16

1 469

String painter

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2476 解题思路大思路：题目要求字符串A转换到字符串B，我们先求空串（即与B串中任意同一位置的字符都不相等的字符串）转换到字符串B最少需要进行多少次操作（此情况为字符串A转换到字符串B的最坏情况，即每个...

2020-10-16

3 701

Two Rabbits（最长回文子序列变形）

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=4745 题解转自 https://my.oschina.net/u/4402652/blog/3524396 题目大意给n个环状的数，A、B两个兔子沿相反的方向走，每次走一步，要求两个兔子每次到达的数要...

2020-10-15

1 579

整数划分

题目链接 NYOJ好像没了，不知道哪里能测评题目及大佬题解链接 https://www.cnblogs.com/mooncode/p/10989408.html 解题思路代码1： dp[i][j]表示前i位数，由j个乘号得到的最大值转移方程： dp[i][j]=max(dp[i][j],dp[k...

2020-10-15

1 609

Palindrome subsequence（求回文子序列的数量）

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=4632 题目大意给你一个长度为N（N≤1000）的字符串，你输出它所有的回文子序列的数量（对10007取模）。只要从字符串 s 中顺序地取出一些字符（不要求连续，可以是 s 本身，不能是空串），不改变他...

2020-10-14

0 1077

Brackets（中文名曰：括号匹配）

题目链接 http://poj.org/problem?id=2955 题目大意我们定义一个字符串序列为“规则的括号序列”当且仅当它满足如下条件：1、空字符串是规则的括号序列；2、如果字符串 s 是一个规则的括号序列，那么 (s) 和 [s] 也是规则的括号序列；3、如果字符串 a 和 b 都是规...

2020-10-14

1 682

石子合并（一圈）四边形不等式优化

题目链接 https://www.luogu.com.cn/problem/P1880 普通dp题解链接 https://blog.nowcoder.net/n/420fe9ffda304281ad58f7abc03fb107 四边形不等式优化很显然，直接区间dp板子搞上的时间复杂度为n^3，n到...

2020-10-14

0 729