01背包问题的动态规划算法、蛮力法和空间优化算法
算法思想： （1）、动态规划算法：解决背包物品价值最大化问题的最优解，是建立在每一个子问题的最优解的前提下完成的。设Value[i,j]表示的是i个物品放进背包容量为j的背包的价值，令i从0增至n（物品总数量），j从0增至c（背包总容量）。Value[n,c]就是我们要的背包价值最大化的解。为了得...
HDU - 1160 FatMouse's Speed 动态规划LIS,路径还原与nlogn优化
HDU - 1160给一些老鼠的体重和速度要求对老鼠进行重排列,并找出一个最长的子序列,体重严格递增,速度严格递减并输出一种方案原题等于定义一个偏序关系 $(a,b)<(c.d)$ 当且仅当 $a<c,b>d$ 然后找出最长链...我们就按照他说的重新排个序,然后找LIS吧,不过还...
动态规划 - 0-1背包问题的算法优化
简单描述 0-1背包问题描述如下： 有一个容量为V的背包，和一些物品。这些物品分别有两个属性，体积w和价值v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。因为最优解中，每个物品都有两种可能的情况，即在背包中或者不存在（背 包中有0个该物品或者 1个），所以...
【BZOJ1150】数据备份（动态规划，凸优化）
【BZOJ1150】数据备份（动态规划，凸优化）题面BZOJ洛谷题解在不考虑\(K\)的情况下很容易\(dp\)如果把\(K\)考虑进状态显然是\(O(n^2)\)级别。所以凸优化一下即可。注意一下是一个下凸函数，所以是没操作一次就要减去一个权值。#include<iostream>#i...
动态规划的优化
目录 动态规划的优化 状态压缩 COGS217USACO Open05 Disease Management 数位动规 区间满足条件的整数个数 HDU2098不要 62 BZ...
BZOJ4409 [Usaco2016 Feb]Circular barn 动态规划 斜率优化
原文链接http://www.cnblogs.com/zhouzhendong/p/8724739.html题目传送门 - BZOJ4409题意有一个N个点的环，相邻两个点距离是1。点顺时针标号为1..N。最初每一个点是空的。要求最终点i存在ri头牛。你有∑ri头牛。你可以选择最多k个点，然后把你的...
【BZOJ5252】林克卡特树（动态规划，凸优化）
【BZOJ5252】林克卡特树（动态规划，凸优化）题面BZOJ(交不了)洛谷题解这个东西显然是随着断开的越来越多，收益增长速度渐渐放慢。所以可以凸优化。考虑一个和\(k\)相关的\(dp\)这个题目可以转换为在树上选择\(K\)条不相交的路径。设\(f[i][0/1/2]\)表示当前点\(i\)，这...
动态规划 FZU2236 树状数组优化
题意： 这题是求一个数列中严格递增子序列的个数。比如数列(1,3,2)的严格递增子序列有(1)、(3)、(2)、(1,3)、(1,2)，共5个。长得一样的但是位置不同的算不同的子序列，比如数列(3,3)的答案是2。 思路： 1、类LIS问题： dp[i] = sigmadp[j] + 1(j...
动态规划初步-01背包问题&&一维数组（空间复杂度优化）
题目链接：51nod1085 背包问题 问题描述： 有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过m的物品，求所有挑选方案中价值总和的最大值。 思路分析： 问题可以看做往一个载重量为m的背包中装入有限数量的物品，求装入物品的最大价值。这里物品的件数都为1，所以每个物品都只...
[luogu3648][bzoj3675][APIO2014]序列分割【动态规划+斜率优化】
题目大意让你把一个数列分成k+1个部分，使分成乘积分成各个段乘积和最大。分析首先肯定是无法开下n \(\times\) n的数组，那么来一个小技巧：因为我们知道k的状态肯定是从k-1的状态转移过来的，而且只从k-1的状态转移过来，那么我们就记录一下k-1和k的状态。然后我们再来动态规划：状态肯定是：...
动态规划初步-01背包问题&&一维数组（空间复杂度优化）
题目链接：51nod1085 背包问题 问题描述： 有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过m的物品，求所有挑选方案中价值总和的最大值。 思路分析： 问题可以看做往一个载重量为m的背包中装入有限数量的物品，求装入物品的最大价值。这里物品的件数都为1，所以每个物品都只...
#动态规划 0-1背包问题空间复杂度优化
上一个版本的0-1背包代码的复杂度：时间复杂度O（n*C）空间复杂度O（n*C） 优化思路如下： 0-1背包问题： F（n，C）考虑将n个物品放入背包为C 的背包，使得价值最大。 状态转移方程：F（i，c） = max(F(i-1 , c) , v(i)+ F(i-1, c- w(i) ) ...
【BZOJ3672】【NOI2014】购票（线段树，斜率优化，动态规划）
【BZOJ3672】【NOI2014】购票（线段树，斜率优化，动态规划）题解首先考虑\(dp\)的方程，设\(f[i]\)表示\(i\)的最优值很明显的转移\(f[i]=min(f[j]+(dep[i]-dep[j])·p[i])+q[i]\)其中满足\(dep[i]-dep[j]\le L[i]\...
最优化算法 - 动态规划算法
动态规划算法简介 动态规划（Dynamic programming）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划算...
UVALive3983[Robotruck] 动态规划 滑动窗口优化
滑动窗口优化 当DP方程形如 dp[i]=min/max(dp[j]+f[j]+f[i]) 时 我们可以把与j无关的元素拿到括号外 即， dp[i]=min/max(dp[j]+f[j]) + f[i] 我们需要维护的是 dp[j]+f[j] 的值 因为要不断的加入i，滑动窗...
【CF739E】Gosha is hunting（动态规划，凸优化）
【CF739E】Gosha is hunting（动态规划，凸优化）题面洛谷CF题解一个\(O(n^3)\)的\(dp\)很容易写出来。我们设\(f[i][a][b]\)表示前\(i\)个怪，两种球用了\(a,b\)个的最大期望，直接用概率转移就好了。然而这样子会TLE飞。发现可以凸优化，对于其中一...
BZOJ_1009_[HNOI2008]_GT考试_(动态规划+kmp+矩阵乘法优化+快速幂)
描述http://www.lydsy.com/JudgeOnline/problem.php?id=1009字符串全部由0~9组成,给出一个串s,求一个长度为n的串,不包含s的种类有多少.分析第一眼以为是组合.然后更滑稽的是用错误的方法手算样例居然算出来是对的...我数学是有多差...题解也是看了好...
BZOJ1911 [Apio2010]特别行动队 - 动态规划 - 斜率优化
欢迎访问~原文出处——博客园-zhouzhendong去博客园看该题解题目传送门UPD(2018-04-01):用Latex重打了公式……题意概括把一个整数序列划分成任意连续的段，使得划分出来的每一段的价值和最大。对于某一段，价值的计算公式为 $V=ax^2+bx+c$，其中 $x$ 为当前段的数值...
动态规划优化
单调队列 简述 函数 f[i] ，转移如下： f[i]=min(g[j]) 其中 g[j] 是关于 j 或 f[j] 的一个函数，且 b[i]≤j<i 维护一个单调递增的队列，队列中的元素下表...
动态规划专题（四）——单调队列优化DP
前言单调队列优化\(DP\)应该还算是比较简单容易理解的吧，像它的升级版斜率优化\(DP\)就显得复杂了许多。基本式子单调队列优化\(DP\)的一般式子其实也非常简单：\[f_i=max_{j=max(i-t,1)}^{i-1}(s(i)+g(j))\]其中\(t\)是一个常数，\(s(i)\)是一...