生之、如舟

动态规划

博弈论(1) 图论(7) 基本算法(29) 并查集(17) 思维(3) 数学(14) 数据结构(5) 数论(18) 最短路(4) 枚举(1) 树状数组(13) 树论(4) 模板(7) 比赛(15) 算法总结(3) 线段树(11) 蓝桥杯(1) 贪心(1)

/ 注册

全部文章 / 动态规划（共8篇）

洛谷 P2196 挖地雷【有向图dp】来自专栏

P2196 挖地雷题目链接：https://www.luogu.com.cn/problem/P2196 思路没错，我又再重学dp。又开始做水题了。这个题数据量很小，可以直接把图进行遍历。每次开始的点分别是1～N。dp[v] = max(dp[v],dp[u] + w[v]) 代码 #inclu...

动态规划

2020-04-20

0 776

HDU2089 不要62 【数位dp】来自专栏

HDU2089 不要62 题解有视频，直接看视频吧数位dp入门视频+HDU2089 代码： #include <iostream> #include <algorithm> #include <string> #include <cstring> #...

视频讲解数位dp

2020-04-10

0 666

删括号【区间dp】

删括号思路代码 #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <map> #include <se...

区间dp

2020-03-26

0 834

【牛客活动每日一题】合并回文子串【区间dp】

合并回文子串活动地址：https://ac.nowcoder.com/discuss/391086?type=101 思路这是一道比较典型的区间dp题目，而区间dp很多时候都是小区间算好了结果，看能不能在此基础上更新大区间，这题也是如此。这里我做了图解：所以我们只需要把初始化工作做好，然后推下去...

区间dp

2020-03-25

0 739

HDU4489 The King’s Ups and Downs 【组合DP】

The King’s Ups and Downs 题意：给你N个人的身高，他们身高各不相同，问排列是高低高低高低、或低高低高低高的方案数是多少？分析此问题的阶段性很容易看出来，就是先求出N = 1的排列数，再求出N=2的排列书，然后再求N=3，再求N = i的排列数时，可能要用到N = 1，N...

组合dp

2020-02-16

0 843

HDU2182 Frog 【基础dp】

HDU2182 Frog 首先，原谅我写这么简单的dp题解，其是是因为我dp基础非常差题意给定4个数N,A,B,K,在[0,N)上每个坐标上都有一些昆虫，现在一只在坐标0的青蛙可以原地不动或通过向右跳A至B步，总共可以跳K次，问最多能够吃到多少只昆虫？分析首先考虑阶段性，跳i步的方案，不会影...

2020-02-15

0 792

HDU1024 Max Sum Plus Plus 【区间dp】【滚动数组】

HDU1024 Max Sum Plus Plus 题意：给你一个N个元素的数列，你需要从中选M个区间，区间之间不能有交叉，问选取的M个区间之和最大值是多少？ (N是1e6的数量级) 分析我们考虑一个数一个数的放，过程是怎么样的。如果当前是选取第i个区间，现在要尝试放入a[j]，那么就会出现两种情...

动态规划区间dp

2020-02-15

0 756

CF855B Marvolo Gaunt's Ring 【DP】

Marvolo Gaunt's Ring Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there...

2020-01-26

0 568