肖先生~

dp

bfs(2) dfs(2) hdu(9) html(2) Oracle(3) poj(2) STL(3) 优先队列(1) 位运算(1) 全排列(1) 前缀和(2) 并查集(1) 数学问题(1) 最小生成树(1) 最短路(1) 未归档(12) 模拟(9) 汇编(1) 牛客(23) 贪心(1) 题解(99)

/ 注册

全部文章 / dp （共6篇）

矩阵连乘之求最优值与构造最优解——呕心沥血篇

矩阵连乘—详细讲解原文来自我的CSDN博客初次接触dp，就看到很多位大佬给出自己的见解，dp算是最难的算法之一吧，主要在于灵活度高，需要自己推出动态规划方程 100个动态规划方程传送门涉及到dp问题那么for循环一般从1开始遍历，这样会好些，虽然目前的我还没理解，但是看到许多大佬写代码都是从...

2020-09-16

0 1271

石子合并——最经典的dp问题

石子合并三大题型任意两堆石子合并，直接手写一个小根堆，每次取前面两个相加，得到的值继续放入优先队列中，直到里面只有一个元素就输出只能合并相邻两堆石子，这就类似于矩阵连乘（传送门），不过还是有一些差别在2的基础上，这些石子形成一个环形，这又是一种新的题型今天记录的是第二种——区间...

2020-09-16

0 4016

最长公共递增子序列——模板

病毒题目描述你有一个日志文件，里面记录着各种系统事件的详细信息。自然的，事件的时间戳按照严格递增顺序排列（不会有两个事件在完全相同的时刻发生）。遗憾的是，你的系统被病毒感染了，日志文件中混入了病毒生成的随机伪事件（但真实事件的相对顺序保持不变）。备份的日志文件也被感染了，但由于病毒采...

2020-09-16

0 654

01背包与部分背包

01背包写在开头有N件物品和一个容量为C的背包，第i件物品的费用是w[i],价值是v[i]，求在不超过背包的最大容量下，求能得到最大的价值 dp[i][j]表示前i件物品放入一个容量为j的背包可以获得的最大价值考虑第i件物品（放与不放）那么就有两种状态。如果不放，那么当前...

2020-09-16

0 595

完美序列（二维dp）

题目描述已知一个长度为l的序列：b1，b2，b3，…，bl (1<=b1<=b2<=b3<=…<=bl<=n)。若这个序列满足每个元素是它后续元素的因子，换句话说就是对于任意的i (2<=i<=l)都满足bi%bi-1=0 (其中“%”代表求余)，则...

2020-09-16

0 892

牛客数学考试（前缀和、动态规划）

数学考试题目分析： 1.连续区间的求和，可以用暴力去枚举，但是最好的方法就是采用前缀和来优化sum[i]=sum[i−1]+a[i]，如果我们要求[l,r]区间的和直接用sum[r]−sum[l−1],前缀和能极大的降低程序的时间复杂度 2.求最优值得话我们就需要用动态规划的思想，在选与...

2020-09-16

0 560