P2722 [USACO3.1] 总分 Score Inflation 题解复盘模块完全背包目标在规定时间内获得最大总分基本信息项目内容题目编号、来源P2722 洛谷 / USACO3.1 Score Inflation训练层级A 模板题知识版块完全背包、动态规划、一维滚动数组解题前 · 关键信号识别维度分析目标、约束、底层结构目标在总时间不超过m的情况下使获得的总分最大。约束每一类题目可以重复选择。底层结构每种物品无限件属于完全背包模型。数据规模1≤n,m≤10000时间复杂度O(n×m)可以通过。候选算法和依据算法完全背包。依据每类题目可以重复选择因此每个物品可以使用无限次。复杂度预判时间复杂度O(n×m)空间复杂度O(m)。解题后 · 外化复盘维度内容实现结构 / 核心思路定义dp[j]表示总时间不超过j时能够获得的最大总分。遍历每一种题目再正序枚举时间容量利用dp[j]max(dp[j],dp[j-t]p)更新答案。错因回溯1. 容易误写成 01 背包把容量倒序枚举。2. 没有识别可以重复选择这一关键条件。3. 状态定义容易写成二维其实一维滚动数组即可。边界和易错点1. 完全背包容量必须正序枚举。2.dp初始值全部为 0因为可以什么都不选。3. 输出dp[m]即可。下次看到什么信号我应该想到这个方法看到可以重复选择“无限供应”“无限件”立即想到完全背包容量正序枚举。AC 完整代码#includeiostream#includealgorithmusingnamespacestd;structnode{intp,t;};intdp[10005];intmain(){intm,n;cinmn;node v[n1];for(inti1;in;i){cinv[i].pv[i].t;}for(inti1;in;i){for(intjv[i].t;jm;j){dp[j]max(dp[j],dp[j-v[i].t]v[i].p);}}coutdp[m];return0;}本题知识点总结1. 状态定义dp[j]表示总时间不超过j时能够获得的最大总分。2. 状态转移dp[j]max(dp[j],dp[j-t]p);表示不选当前题目再做一题当前类型。取最大值。3. 为什么正序枚举因为当前题目可以重复选择。例如时间6 一道题 耗时2 得分5更新过程dp[2]5 ↓ dp[4]dp[2]510 ↓ dp[6]dp[4]515因此必须正序for(intjt;jm;j)4. 与01背包区别类型每件物品容量枚举01背包只能选择一次倒序完全背包可以无限选择正序一句话总结看到物品可以无限选择立即想到完全背包定义dp[j]表示容量为j的最优值容量正序枚举完成状态转移。P2918 [USACO08NOV] Buying Hay S 题解复盘模块动态规划目标购买至少 H 磅干草使总花费最小基本信息项目内容题目编号、来源P2918 洛谷 / USACO08NOV Buying Hay S训练层级B 变形题知识版块完全背包、至少装满、最小费用、状态扩展解题前 · 关键信号识别维度分析目标、约束、底层结构目标购买至少H磅干草并使总花费最小。约束每种干草包可以购买无限多个。底层结构每种物品可以无限选择因此属于完全背包但目标不是“恰好装满”而是“至少达到 H”所以需要额外处理超过 H 的状态。数据规模N≤100H≤50000单包最大重量5000。使用一维完全背包可以满足要求。候选算法和依据算法完全背包 至少装满。每个公司货源无限因此容量正序枚举为了覆盖“超过 H 才达到要求”的情况将状态范围扩展到HmaxP。复杂度预判时间复杂度约为O(N×(HmaxP))空间复杂度O(HmaxP)。解题后 · 外化复盘维度内容实现结构 / 核心思路定义dp[j]表示恰好购买j磅干草时的最小花费。先将所有状态初始化为无穷大dp[0]0。每种干草可以无限购买所以正序枚举重量dp[j]min(dp[j],dp[j-p]c)。由于题目要求至少 H而不是恰好 H因此计算到HmaxP最后在[H,HmaxP]中寻找最小花费。错因回溯1. 一开始把dp初始化成10000但真实答案可能远大于这个值应该使用足够大的INF。2. 忘记设置dp[0]0导致所有状态无法从合法起点转移。3. 一开始只枚举到H无法处理“必须超过 H 才能满足要求”的情况。4. 不能直接输出dp[H]因为最优方案可能购买H1、H2等重量。边界和易错点1. 每种干草包无限供应因此容量正序枚举。2. 求最小值时除dp[0]外都要初始化为INF。3. 状态需要扩展到HmaxP。4. 最终答案是在所有j≥H的可达状态中取最小值。下次看到什么信号我应该想到这个方法看到“每种物品无限”“至少达到某个容量”“求最小费用”想到完全背包 至少装满容量正序并额外枚举超过目标容量的状态。AC 完整代码#includeiostream#includequeue#includealgorithm#includevector#includeiomanipusingnamespacestd;structnode{intp,c;};constintmaxx1e9;intdp[1000000];intmain(){intN,H;cinNH;node v[N1];intmaxn0;for(inti1;iN;i){cinv[i].pv[i].c;maxnmax(maxn,v[i].p);}fill(dp,dp1000000,maxx);dp[0]0;for(inti1;iN;i){for(intjv[i].p;jHmaxn;j){dp[j]min(dp[j],dp[j-v[i].p]v[i].c);}}longlongansmaxx;for(intiH;iHmaxn;i){ansmin(ans,(longlong)dp[i]);}coutans;return0;}本题知识点总结1. 状态定义dp[j]表示恰好购买j磅干草所需要的最小花费。注意这里不是“不超过 j”而是“恰好达到 j”。2. 初始化因为要求最小费用所以不能默认初始化成 0。应写fill(dp,dpMAXN,INF);dp[0]0;其中dp[0]0;表示什么都不买购买 0 磅干草花费为 0。这是所有后续状态转移的起点。3. 状态转移当前干草包重量 p 价格 c那么dp[j]min(dp[j],dp[j-p]c);表示原来已经买到j-p磅再购买一包当前干草就可以达到j磅。4. 为什么容量正序因为每种干草可以购买无限多包。例如一包重量 3 价格 2正序时dp[3] ↓ dp[6] 可以继续利用刚更新的 dp[3] ↓ dp[9] 又可以继续利用 dp[6]从而实现同一种干草重复购买。所以必须for(intjp;jlimit;j)5. 为什么不能只算到 H因为题目要求至少 H不一定能刚好买到 H。例如H10只有一种草包重量6能够购买的重量6 12 18 ...不存在恰好 10。正确方案是12 ≥ 10所以必须允许状态超过 H。6. 为什么只需要算到 HmaxP设最后一包干草的重量最多为maxP一个“第一次达到至少 H”的方案其最终重量最多为H maxP - 1所以计算到HmaxP一定足够覆盖最优答案。7. 最终答案不能直接coutdp[H];而应该for(intjH;jHmaxP;j){ansmin(ans,dp[j]);}因为任何重量j≥H都满足题意。与普通完全背包对比模型目标最终答案普通完全背包容量不超过 H价值最大dp[H]恰好装满恰好达到 Hdp[H]Buying Hay至少达到 H费用最小min(dp[H...HmaxP])一句话总结看到“物品无限 至少达到目标 求最小费用”想到完全背包的“至少装满”变形容量正序状态扩展到目标容量之外最后对所有j≥H的状态取最小值。P1279 [CHCI 2002 National Competition #2 Seniors] 字串距离 题解复盘模块字符串动态规划目标在两个字符串中插入若干空格使两个扩展串的总距离最小基本信息项目内容题目编号、来源P1279 洛谷 / CHCI 2002 National Competition #2 Seniors训练层级B 变形题知识版块字符串DP、编辑距离变形、二维DP、序列对齐解题前 · 关键信号识别维度分析目标、约束、底层结构目标允许在两个字符串任意位置插入空格使最终两个等长扩展串的距离总和最小。约束字符与字符的代价为 ASCII 差的绝对值字符与空格的代价固定为K。底层结构每一步只可能让两个字符直接对应、A 中字符与空格对应、或空格与 B 中字符对应因此是典型的二维字符串 DP。数据规模两个字符串长度均不超过 2000使用O(nm)二维 DP 可以满足要求。候选算法和依据算法字符串DP / 编辑距离变形。依据当前状态只与左、上、左上三个状态有关且目标是求最小代价。复杂度预判时间复杂度O(nm)空间复杂度O(nm)。解题后 · 外化复盘维度内容实现结构 / 核心思路定义dp[i][j]表示字符串 A 的前i个字符与字符串 B 的前j个字符进行最优扩展匹配后的最小距离。每个状态考虑三种情况字符对字符、字符对空格、空格对字符取三者最小值。错因回溯1. 容易把a[i]和b[i]比较实际上当前状态是dp[i][j]应该比较a[i]和b[j]。2. 给字符串前面补空格后要注意真实长度仍然是原长度。3.dp数组不需要开到10005×10005题目长度最多 2000开2005×2005即可。边界和易错点1.dp[i][0]i*K表示 A 的前 i 个字符全部与空格匹配。2.dp[0][j]j*K表示 B 的前 j 个字符全部与空格匹配。3. 空格与空格不需要考虑因为不会消耗任何字符也不会产生额外代价。4. 字符直接匹配的代价是abs(a[i]-b[j])。下次看到什么信号我应该想到这个方法看到“两个字符串、允许插入空格、字符对应有代价、求最小总代价”想到编辑距离类字符串DP / 序列对齐DP。AC 完整代码#includeiostream#includealgorithm#includecmathusingnamespacestd;intdp[2005][2005];intmain(){string a,b;intk;cinabk;intma.size();intnb.size();a a;b b;for(inti0;im;i){dp[i][0]i*k;}for(inti0;in;i){dp[0][i]i*k;}for(inti1;im;i){for(intj1;jn;j){intxabs(a[i]-b[j]);dp[i][j]min(dp[i-1][j-1]x,min(dp[i-1][j]k,dp[i][j-1]k));}}coutdp[m][n];return0;}本题知识点总结1. 状态定义dp[i][j]表示A 的前i个字符和 B 的前j个字符经过最优扩展后得到的最小距离。2. 三种转移情况一字符和字符对应A[i] B[j]代价abs(a[i]-b[j])所以dp[i][j]dp[i-1][j-1]abs(a[i]-b[j]);情况二A 的字符和空格对应A[i] 空格代价为K因此dp[i][j]dp[i-1][j]K;情况三空格和 B 的字符对应空格 B[j]代价同样为K因此dp[i][j]dp[i][j-1]K;3. 最终转移方程dp[i][j]min(dp[i-1][j-1]abs(a[i]-b[j]),min(dp[i-1][j]k,dp[i][j-1]k));4. 为什么dp[i][0]i*K当 B 为空串时A abc B 只能匹配成a b c - - -每个字符和空格的距离都是K。所以总代价K K K 3K因此dp[i][0]i*K;同理dp[0][j]j*K;5. 为什么不用考虑空格和空格如果两个字符串同一位置都插入空格- -代价为 0。但是它不消耗 A 的字符不消耗 B 的字符不改变总距离。所以没有任何意义可以直接删掉这一对空格。因此 DP 只需要考虑三种有效匹配字符 - 字符 字符 - 空格 空格 - 字符与编辑距离、相似基因对比题目状态目标三种操作P2758 编辑距离dp[i][j]最小操作数删除、插入、修改P1140 相似基因dp[i][j]最大相似度字符-字符、字符-空格、空格-字符P1279 字串距离dp[i][j]最小距离字符-字符、字符-空格、空格-字符本质上它们都是两个字符串前缀之间的最优对齐问题。一句话总结看到“两个字符串 可以插空格 对应位置有代价 求最优”想到二维字符串 DP状态dp[i][j]表示两个前缀的最优答案转移从左、上、左上三个方向取最优。