G7014 [GESP202506 七级] 调味平衡 题解

知识点：0-1背包、差值状态、动态规划。

解题思路

以甜酸差a-b为状态，用偏移量支持负数；dp[d]为该差值下最大的甜酸总和。每种调料复制一份旧DP后做选或不选转移，最后取差0。

为什么正确

每个子集的差值可相加，总量也可相加；保留同差值最大总量可覆盖最优平衡方案。

易错点

差值允许负数；更新必须基于旧数组，不能让同一调料被重复使用；空集初始差0、收益0。

复杂度

设D为绝对差之和，时间O(nD)，空间O(D)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<pair<int,int>>a(n);
    int lim=0;
    for(auto &x:a) {
        cin>>x.first>>x.second;
        lim+=abs(x.first-x.second);
    }
    vector<int>dp(2*lim+1,-1000000000);
    dp[lim]=0;
    for(auto [a,b]:a) {
        auto ndp=dp;
        for(int i=0;i<=2*lim;i++)if(dp[i]>=0&&i+a-b>=0&&i+a-b<=2*lim)ndp[i+a-b]=max(ndp[i+a-b],dp[i]+a+b);
        dp.swap(ndp);
    }
    cout<<dp[lim];
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。