Oiclass P1255 题解
又是一个我背不动的背包 这次是 0/1 背包 plus——多重背包，下面是经典的五步 1. 划分阶段 以每一个物品为一个阶段，表示这个物品前的物品的最大值（包括这个物品自身）。 2. 确定状态和状态变量 搞一个一维数组 \(f\) ，即 \(f_i\) 表示第 \(1\) 个物品到第 \(i\) 个物品之间（算头算尾）的最优解，也就是在空间不超过 \(v\) 的情况下最大的价值总和。 3. 确定决
CodingCow's Blog - Code solves everything
Oiclass P1246 题解
你说为什么 01 背包模板不是偷东西呢？ 额，搞错了，再来！ 1. 划分阶段 一共划分 \(M\) 个阶段，每个阶段表示在这个阶段可以采的最多的草药 2. 确定状态和状态变量 状态变量就用一个二维数组 \(f\) 吧，也就是说 \(f_{i,\ j}\) 表示前 \(i\) 颗草药在前 \(j\) 的时间可以获得最大价值，也就是说我们想求的是用 \(j\) 的时间，如何在 \(a_{1 \to i
Oiclass P1928 题解
这道题简直拓宽了回文这个词的定义 天哪，我见回文数，回文分解，回文日，还真的没有见过回文词，而且这个词还毫无任何美感可言，其他回文可都是很优雅的呀。不吐槽了，进入正题 1. 划分阶段 这里定义两个字符串，\(a\) 和 \(b\) ，\(a\) 是输入的字符串，\(b\) 是 \(a\) 的反串。对于这两个字符串，一共有 \(2 \times a.length()\) 种状态，也可以说有 \(a.
Oiclass P1241 题解
这次是 LIS 的兄弟 LCS（最长公共子序列） 一个词概括，模板题。但是，模板题也很难啊啊啊啊啊啊。又是经典的五步： 1. 划分状态 假设 \(a\) 和 \(b\) 是本次主角字符串（好想把他们拉出去斩了） ，那么一共有 \(a.length() \times b.length()\) 种状态，每一种状态表示下标 \(i\) 之前的 \(a\) 的子串（即 a.substr(0, i)）与下标
Oiclass P1240 题解
这道题是真的难啊 这道题目中 \(\Huge 相邻\) 这个该 * 的词很容易 让人误以为这道题有后效性，当时我们全班都认为这道题有后效性，然而我们美丽的又和蔼的 Lily 却和我们说没有。仔细分析后发现，直接观察确实这道题目有后效性，但是如果深入分析，就会发现，只有前面的一项会影响它本身，在计算后一项的时候，对他本身并不会产生影响，他始终是最优解，行，确定能用 DP 了，开工！！！！ 1. 划分
Oiclass P1242 题解
这道题真的离谱 1. 划分阶段 对于这道题目，我以每一个字母为一个阶段，表示第一个字符串的前 \(i\) 个字母和第二个字符串的前 \(j\) 个字母之间的编辑距离（定义见题目） 2. 状态和状态变量 定义数组 \(f\) 用于存储状态，即 \(f_{i,\ j}\) 表示一个阶段（也就是(1) 里面提到的阶段），同时 \(a,b\) 分别是输入的两个字符串 3. 确定状态转移方程 这就是最难的部
Oiclass P1263 题解
这真是一场愉快的传球游戏 再次是传统的五步 1. 划分阶段 这里我划分的状态是：每次传球完一种状态 2. 确定状态和状态变量 对于状态变量，我定义一个二维数组 \(f\) ，对于 \(f_{i,\ j}\) 他表示的是在 \(i\) 次传球后，\(j\) 手上的球的数量。 3. 确定决策和状态转移公式 对于这道题，决策的方式稍稍有那么一点点复杂，对于一种状态 （\(f_{i,\ j}\)）它有以下
Oiclass P1993 题解
又是一道 DP 看到题目，我的第一反应就是：这鼹鼠是什么玩意儿？ 额，\(\Huge 搞错了\) 再来 下面是传统的五步 1. 划分阶段 以每一只耐造的鼹鼠为一个阶段，表示在这只鼹鼠前面（包括这只鼹鼠）可以打到的鼹鼠的数量 2. 确定状态和状态变量 这里使用两个数组 \(f,\ a\) ，分别存储状态和输入的数据 3. 确定决策和状态转移公式 因为每一只鼹鼠都可以和他前面的任何一只鼹鼠结合，所以我