胖男孩 DP

题解 f[i][j][k]表示分别取前i j k个字符时的最长公共子序列 误打的字符不超过3个,最坏情况 打了一个正确的+三个错误的+三个错误的+一个正确的 因此在加三重循环x y z枚举上一个正确的字符的位置 CODE ...

洛谷 P1108 低价购买 DP

题解 b[i]表示前i-1天最大购买次数 f[i]表示前i-1天方案数 讲下怎么处理看起来相同的状态 因为同样的价格,肯定是靠后的更优,所以用isbest[i]表示当前天选到价格i是不是更靠后的方案, 循环j从i-1~...

hdu 3033 I love sneakers! 背包

题解 dp[i][j]表示购买完第i个品牌的运动鞋,花费j时的最大价值 注意价格为0的情况,先从当前层转移,再从上一层转移就不会算两遍了 初始:dp[0][j]=0 dp[i][j]=-1; 这样一定会从 上一层价值+本层物品价...

tyvj P1050 最长公共子序列

[latexpage] 题解 f[i][j]表示a字符串前i个字符与b字符串前j个字母组成的最长公共子序列(具体写的时候是从0~len-1) \[\begin{array}{l} dp\left[ i \right]\left[ j \right] = dp[i - 1][j - 1] + 1(a\le...

luogu P1280 尼克的任务

[latexpage] 题解 这个推法好像有点奇怪 f[i]表示第i分钟时获得的做大空闲时间 用一个vector to[i]存储从i开始的任务结束时间 \[\begin{array}{l} f[i] = \max (f[i - 1] + 1,f[i])(to[i].size = = 0...

导弹拦截 贪心

题解 这道题用贪心过了。 f数组存储当前所有系统所能达到的最大高度 倒序对所有导弹高度进行处理,若当前导弹高度高于所有系统所能达到的最大高度,就新添加一套拦截系统,否则对f数组进行二分查找,找到...

POJ 2411 铺砖块 状压DP

题解 \[f[i,sta]\]表示已填满第i行,且对下一行的影响为sta时的状态数 init过程预处理相邻两行的可行状态 1表示已经铺满0表示没有铺 当上一行对这一行的影响为0时 下一行的状态为1 (竖铺1块) 当上一...

【模板题】找啊找啊找GF

题解  多维背包 数组t[j][k]记录时间 数组dp[j][k]记录背包内物品数量 保证数量的前提下,时间最少 CODE   [crayon-6002d1b92fd4f839310938/] 题目描述 题目背景 "找啊找啊找GF,找到一个...

【模板题】01背包

题解 定义  :      如果 这个物品无法被放入背包内   () ans: 伪代码: [crayon-6002d1b93046a059797830/] 时间复杂度 空间复杂度 使用滚动数组得到空间复杂度 代码 [crayon-600...