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 完整代码
#include<iostream>#include<algorithm>usingnamespacestd;structnode{intp,t;};intdp[10005];intmain(){intm,n;cin>>m>>n;node v[n+1];for(inti=1;i<=n;i++){cin>>v[i].p>>v[i].t;}for(inti=1;i<=n;i++){for(intj=v[i].t;j<=m;j++){dp[j]=max(dp[j],dp[j-v[i].t]+v[i].p);}}cout<<dp[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]+5=10 ↓ dp[6]=dp[4]+5=15因此必须正序：
for(intj=t;j<=m;j++)4. 与01背包区别
| 类型 | 每件物品 | 容量枚举 |
|---|---|---|
| 01背包 | 只能选择一次 | 倒序 |
| 完全背包 | 可以无限选择 | 正序 |
一句话总结
看到"物品可以无限选择"，立即想到完全背包；定义
dp[j]表示容量为j的最优值，容量正序枚举完成状态转移。
P2918 [USACO08NOV] Buying Hay S 题解复盘
模块：动态规划
目标：购买至少 H 磅干草，使总花费最小
基本信息
| 项目 | 内容 |
|---|---|
| 题目编号、来源 | P2918 洛谷 / USACO08NOV Buying Hay S |
| 训练层级 | B 变形题 |
| 知识版块 | 完全背包、至少装满、最小费用、状态扩展 |
解题前 · 关键信号识别
| 维度 | 分析 |
|---|---|
| 目标、约束、底层结构 | 目标：购买至少H磅干草，并使总花费最小。约束：每种干草包可以购买无限多个。 底层结构：每种物品可以无限选择，因此属于完全背包；但目标不是“恰好装满”，而是“至少达到 H”，所以需要额外处理超过 H 的状态。 |
| 数据规模 | N≤100，H≤50000，单包最大重量5000。使用一维完全背包可以满足要求。 |
| 候选算法和依据 | 算法：完全背包 + 至少装满。 每个公司货源无限，因此容量正序枚举；为了覆盖“超过 H 才达到要求”的情况，将状态范围扩展到 H+maxP。 |
| 复杂度预判 | 时间复杂度约为O(N×(H+maxP))，空间复杂度O(H+maxP)。 |
解题后 · 外化复盘
| 维度 | 内容 |
|---|---|
| 实现结构 / 核心思路 | 定义dp[j]表示恰好购买j磅干草时的最小花费。先将所有状态初始化为无穷大，dp[0]=0。每种干草可以无限购买，所以正序枚举重量：dp[j]=min(dp[j],dp[j-p]+c)。由于题目要求至少 H，而不是恰好 H，因此计算到H+maxP，最后在[H,H+maxP]中寻找最小花费。 |
| 错因回溯 | 1. 一开始把dp初始化成10000，但真实答案可能远大于这个值，应该使用足够大的INF。2. 忘记设置 dp[0]=0，导致所有状态无法从合法起点转移。3. 一开始只枚举到 H，无法处理“必须超过 H 才能满足要求”的情况。4. 不能直接输出 dp[H]，因为最优方案可能购买H+1、H+2等重量。 |
| 边界和易错点 | 1. 每种干草包无限供应，因此容量正序枚举。 2. 求最小值时，除 dp[0]外都要初始化为INF。3. 状态需要扩展到 H+maxP。4. 最终答案是在所有 j≥H的可达状态中取最小值。 |
| 下次看到什么信号，我应该想到这个方法 | 看到“每种物品无限”“至少达到某个容量”“求最小费用”，想到：完全背包 + 至少装满，容量正序，并额外枚举超过目标容量的状态。 |
AC 完整代码
#include<iostream>#include<queue>#include<algorithm>#include<vector>#include<iomanip>usingnamespacestd;structnode{intp,c;};constintmaxx=1e9;intdp[1000000];intmain(){intN,H;cin>>N>>H;node v[N+1];intmaxn=0;for(inti=1;i<=N;i++){cin>>v[i].p>>v[i].c;maxn=max(maxn,v[i].p);}fill(dp,dp+1000000,maxx);dp[0]=0;for(inti=1;i<=N;i++){for(intj=v[i].p;j<=H+maxn;j++){dp[j]=min(dp[j],dp[j-v[i].p]+v[i].c);}}longlongans=maxx;for(inti=H;i<=H+maxn;i++){ans=min(ans,(longlong)dp[i]);}cout<<ans;return0;}本题知识点总结
1. 状态定义
dp[j]表示：
恰好购买
j磅干草所需要的最小花费。
注意这里不是“不超过 j”，而是“恰好达到 j”。
2. 初始化
因为要求最小费用，所以不能默认初始化成 0。
应写：
fill(dp,dp+MAXN,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(intj=p;j<=limit;j++)5. 为什么不能只算到 H？
因为题目要求：
至少 H不一定能刚好买到 H。
例如：
H=10只有一种草包：
重量6能够购买的重量：
6 12 18 ...不存在恰好 10。
正确方案是：
12 ≥ 10所以必须允许状态超过 H。
6. 为什么只需要算到 H+maxP？
设最后一包干草的重量最多为：
maxP一个“第一次达到至少 H”的方案，其最终重量最多为：
H + maxP - 1所以计算到：
H+maxP一定足够覆盖最优答案。
7. 最终答案
不能直接：
cout<<dp[H];而应该：
for(intj=H;j<=H+maxP;j++){ans=min(ans,dp[j]);}因为：
任何重量
j≥H都满足题意。
与普通完全背包对比
| 模型 | 目标 | 最终答案 |
|---|---|---|
| 普通完全背包 | 容量不超过 H，价值最大 | dp[H] |
| 恰好装满 | 恰好达到 H | dp[H] |
| Buying Hay | 至少达到 H，费用最小 | min(dp[H...H+maxP]) |
一句话总结
看到“物品无限 + 至少达到目标 + 求最小费用”，想到完全背包的“至少装满”变形：容量正序，状态扩展到目标容量之外，最后对所有
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 完整代码
#include<iostream>#include<algorithm>#include<cmath>usingnamespacestd;intdp[2005][2005];intmain(){string a,b;intk;cin>>a>>b>>k;intm=a.size();intn=b.size();a=" "+a;b=" "+b;for(inti=0;i<=m;i++){dp[i][0]=i*k;}for(inti=0;i<=n;i++){dp[0][i]=i*k;}for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){intx=abs(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));}}cout<<dp[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]表示两个前缀的最优答案，转移从左、上、左上三个方向取最优。
