这是我写的第2个正式题解

---

【A75422】[GESP202506 七级] 调味平衡

题目链接

点这里

题目大意

现在有n种食材，依次以1,2,...,n编号
第i种食材酸度为a_i，甜度为b_i
对于每种食材，可加可不加。
要求：加入食材酸度总和=甜度总和
求：满足以上条件下能获得的酸度+甜度总和的最大值

解题思路

1. 算法选择

因为每种食材都可以选/不选，因此不难看出这是一道0/1背包问题，但只不过加了个限制条件

2. 核心思路

dp定义：
$定义dp[i][j]为考虑前i种食材，酸度-甜度差值为j时的最大酸甜度总和$

dp初始化：
先将整个dp数组定义为极小值，但对于dp[0][差值为0]需要初始化为0，否则后续无法更新最大值

对于这里为什么不是dp[0][0]初始化，后面再说

状态转移方程：
对于每个$dp[i][j]$，无非就两种情况
一种是不选第i个食材，则$dp[i][j]=max(dp[i][j], dp[i - 1][j])$
一种是选第i个食材，则$dp[i][j] = max(dp[i][j], dp[i - 1][上一次选择酸甜之差]+酸甜总和)$

这里就要说到一个问题：数组越界
如果 $酸度-甜度之差\le0$，那么这时候dp[i-1][酸甜之差]就会越界
因此我们要设置一个偏移量——$100（n \le 100） \times 500（a_i,b_i\le500） = 50000$
那这样，我们的状态转移方程就变成了

// 外层循环第i个物品
for (int tempj = 0;tempj <= 100000;tempj++){// 添加偏移量后的j
    int j = tempj - 50000;// 真正的j
    dp[i][tempj] = max(dp[i][tempj], dp[i - 1][tempj]);// 不选
    int prej = j - (a[i] - b[i]);// 选之前的真正差值
    int preidx = prej + 50000;// 放到dp数组中的位置
    if (preidx >= 0 && preidx <= 100000){// 尽管有偏移量，也不能越界
        dp[i][tempj] = max(dp[i][tempj], dp[i - 1][preidx] + (a[i] + b[i]));// 状态转移方程
    }
}

最终答案：$dp[n][50000] \to 偏移量后为50000\to 本质上就是酸甜之差为0$

3. 复杂度分析

• 时间复杂度：$O(n\times100000)$
• 空间复杂度：$O(n\times100000)$

易错点/坑点

1. 这题最易错的点就是dp定义和偏移量的问题

AC 代码

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 111, M = N * 500 * 2;
int a[N], b[N];
int dp[N][M];
// 初始化部分

int main(){

    cin >> n;
    for (int i = 1;i <= n;i++){
        cin >> a[i] >> b[i];
    }
    // 输入部分

    memset(dp, -0x3f, sizeof(dp));
    dp[0][50000] = 0;
    // dp数组初始化部分

    for (int i = 1;i <= n;i++){
        for (int tempj = 0;tempj <= 100000;tempj++){
            int j = tempj - 50000;
            dp[i][tempj] = max(dp[i][tempj], dp[i - 1][tempj]);
            int prej = j - (a[i] - b[i]);
            int preidx = prej + 50000;
            if (preidx >= 0 && preidx <= 100000){
                dp[i][tempj] = max(dp[i][tempj], dp[i - 1][preidx] + (a[i] + b[i]));
            }
        }
    }
    // 状态转移方程部分

    cout << dp[n][50000];
    // 输出结果部分    
    
    return 0;
}