这是我写的第2个正式题解
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
【A75422】[GESP202506 七级] 调味平衡
题目链接
点这里
题目大意
现在有n种食材，依次以1,2,...,n编号
第i种食材酸度为a_i，甜度为b_i
对于每种食材，可加可不加。
要求：加入食材酸度总和=甜度总和
求：满足以上条件下能获得的酸度+甜度总和的最大值
解题思路
1. 算法选择
因为每种食材都可以选/不选，因此不难看出这是一道0/1背包问题，但只不过加了个限制条件
2. 核心思路
> dp定义：
> 定义dp[i][j]为考虑前i种食材，酸度−甜度差值为j时的最大酸甜度总和定义dp[i][j]为考虑前i种食材，酸度-甜度差值为j时的最大酸甜度总和定义dp[i][j]为考虑前i种食材，酸度−甜度差值为j时的最大酸甜度总和
> dp初始化：
> 先将整个dp数组定义为极小值，但对于dp[0][差值为0]需要初始化为0，否则后续无法更新最大值
对于这里为什么不是dp[0][0]初始化，后面再说
> 状态转移方程：
> 对于每个dp[i][j]dp[i][j]dp[i][j]，无非就两种情况
> 一种是不选第i个食材，则dp[i][j]=max(dp[i][j],dp[i−1][j])dp[i][j]=max(dp[i][j], dp[i - 1][j])dp[i][j]=max(dp[i][j],dp[i−1][j])
> 一种是选第i个食材，则dp[i][j]=max(dp[i][j],dp[i−1][上一次选择酸甜之差]+酸甜总和)dp[i][j] = max(dp[i][j], dp[i - 1][上一次选择酸甜之差]+酸甜总和)dp[i][j]=max(dp[i][j],dp[i−1][上一次选择酸甜之差]+酸甜总和)
这里就要说到一个问题：数组越界
如果 酸度−甜度之差≤0酸度-甜度之差\le0酸度−甜度之差≤0，那么这时候dp[i-1][酸甜之差]就会越界
因此我们要设置一个偏移量——100（n≤100）×500（ai,bi≤500）=50000100（n \le 100） \times 500（a_i,b_i\le500） = 50000100（n≤100）×500（ai ,bi ≤500）=50000
那这样，我们的状态转移方程就变成了
> 最终答案：dp[n][50000]→偏移量后为50000→本质上就是酸甜之差为0dp[n][50000] \to 偏移量后为50000\to 本质上就是酸甜之差为0dp[n][50000]→偏移量后为50000→本质上就是酸甜之差为0
3. 复杂度分析
* 时间复杂度：O(n×100000)O(n\times100000)O(n×100000)
* 空间复杂度：O(n×100000)O(n\times100000)O(n×100000)
易错点/坑点
1. 这题最易错的点就是dp定义和偏移量的问题
AC 代码
