差值 dp 入门

ylch · 2025-02-03 16:36:49 · 算法·理论

引入

有一类问题：两个人交替选 n 个数 a[1 \dots n]，要使得每个人分得的数大小之和相等（或差值尽可能小），同时尽可能保证分得的总金额尽可能大。

这类问题的解法之一是 dp。

有一个通用状态：设 f[i][j][k] 表示前 i 个数，先手得到的数值之和为 j，后手得到的数值之和为 k 时两人一共得到的最大答案。

我们可以优化状态：设 f[i][j] 表示前 i 个数，两人分到的数差值为 j 时先手能得到的最大钱数。因为我们只关注相对大小，而不关注具体数值。

注：由于状态中存在“差值”概念，所以这类问题被称为差值 dp，属于 01 背包的状态优化版。这类问题的一般暗示会有：谁追上谁，谁减去谁，谁加上谁，谁和谁相等/接近……

如果要保证拿到的数大小之和相等，答案即为 f[n][0]。

考虑转移：

1. 不用第 i 个数：f[i][j]=f[i-1][j]；
2. 把第 i 个数给先手：f[i][j]=f[i-1][j-a[i]]+a[i]；
3. 把第 i 个数给后手：f[i][j]=f[i-1][j+a[i]]。

还有一个问题，j-a[i] 有可能为负，而数组下标显然不能是负数，有两种解决方法：

1. 平移法。假设值域 w=\sum a[i]，考虑把第二维下标所有的数都加上 w，这样负数存储时就变成了正数。相当于把值域往正方向平移了 w 个单位长度。注意此时代表 0 的数是 w，所以最终答案应该是 f[n][w]。

2. 绝对值法。当最终答案要求两个人取的数之和相等时，我们无需知道大小关系（因为最后一定都相等），所以考虑在减差值时加上一个绝对值来转正：f[i][j]=f[i-1][abs(j-a[i])]+a[i]。

以上两种方法的使用视情况而定。时间复杂度为 O(w \times n)（这也是 01 背包问题的普遍复杂度）。

注：有时改变 dp 状态的意义会对做题更有帮助，请大家学会随机应变。但核心思想是不变的。有一些常见的套路在下面例题中给大家介绍。

例题

例1.塔

这就是我们上面问题的模板。代码中顺便展示记忆化搜索+剪枝的解法：

/*
1.差值dp
设dp[i][j]表示选了前i个物品，两堆积木差值为j时第一堆积木的高度（这个状态是精髓！）
那么显然有以下三种转移：
不选i，      dp[i][j]<-dp[i-1][j]
选i放第一堆，dp[i][j]<-dp[i-1][j-a[i]]+a[i]
选i放第二堆，dp[i][j]<-dp[i-1][j+a[i]]      // 注意这里不要加上a[i]，因为状态存的是第一堆积木的高度

还有一个问题，因为存储的是差值，所以第二维可能有负数。
考虑将第二维向上平移500000个，这样0~499999的是负数，500001~1000000的是正数，500000表示0

又发现第i行的状态转移只和第i-1行有关，可以滚动数组优化空间

------------------------------------------------------------

2.爆搜优化：剪枝+记忆化
不加优化爆搜就是01选择类的dfs，判断每个物品是选给第一堆还是第二堆，时间复杂度O(2^n)
考虑先剪枝一下:
1.可行性剪枝。如果当前第一堆加上剩余所有都达不到第二堆高度，显然无解。第二堆同理
2.最优性剪枝。记录当前的最大答案ans，如果第一堆加上剩余所有方块都无法达到ans，显然这个状态不优。
  如果两堆和剩下所有加起来无法达到2*ans，显然也不优。第二堆同理
3.搜索顺序剪枝。发现答案具有不依赖顺序的特点（按照不同的顺序叠都行，只要最后高度不一样就行）
  所以考虑对所有积木降序排序。这样DFS时会优先选择较大的数。较大的数更容易接近目标值，从而更快地触发剪枝条件，减少无效搜索。
然后发现dfs会重复搜到许多一样的状态，所以考虑用一个记忆化数组存储当前状态的答案，这样就可以极大优化时间复杂度
由于这道题值域过大，考虑用map来实现记忆化

------------------------------------------------------------

发现不行的情况即为最大高度为0的情况，输出-1
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxh = 1e6 + 7, zero = 5e5;

int n, a[60];

// dp解法
void dp(){
    vector <int> f(maxh,-1e9); // f表示前一行(i-1)，g表示当前行(i)
    vector <int> g(maxh,-1e9); // 初始化为极小值，避免出错

    f[zero] = 0; // 给一个初状态f[0]
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= 1e6; j ++){ // 只要遍历到所有元素的和即可
            g[j] = max(g[j], f[j]);                   // f[i][j]=max(f[i][j],f[i-1][j])
            if(j >= a[i]){
                g[j] = max(g[j], f[j - a[i]] + a[i]); // f[i][j]=max(f[i][j],f[i-1][j-a[i]]+a[i])
            }
            if(j + a[i] <= 1e6){
                g[j] = max(g[j], f[j + a[i]]);        // f[i][j]=max(f[i][j],f[i-1][j+a[i]])
            }
        }
        f = g; // 把值滚动给下一行
        fill(g.begin(),g.end(),-1e9); // 重置g数组的值
    }
    cout << (f[zero] == 0? -1 : f[zero]) << '\n'; // 此时因为g的值已经没了，所以要输出f
}

// -------------------------------------------------------------------

// 搜索解法
int ans = -1e9;
int s[60]; // s是前缀和数组
map< tuple<int,int,int> , int > vis; // 考虑用map存状态

int dfs(int now, int h1, int h2){
    // 终止条件
    if(now == n + 1){
        if(h1 == h2){ ans = max(ans, h1); return h1; }
        else return -1;
    }

    // 记忆化
    tuple <int,int,int> t = {now, h1, h2};
    if(vis.count(t)){
        return vis[t];
    }

    // 剪枝
    if(h1+h2 + s[n]-s[now-1] <= 2*ans)  return -1;
    if(h1 + s[n]-s[now-1] <= ans)       return -1;
    if(h2 + s[n]-s[now-1] <= ans)       return -1;
    if(h1 + s[n]-s[now-1] < h2)         return -1;
    if(h2 + s[n]-s[now-1] < h1)         return -1;

    // 返回即为三种情况取max
    return vis[t] = max({ 0/*避免都是-1，和0取一下max*/,
        dfs(now+1,h1+a[now],h2), dfs(now+1,h1,h2+a[now]), dfs(now+1,h1,h2) });
}

void search(){
    sort(a + 1, a + n + 1, greater<>()); // 降序排序，可以加快搜索（这样不合法的更容易被剪枝）
    for(int i = 1; i <= n; i ++){
        s[i] = s[i - 1] + a[i];
    }
    int sum = dfs(1, 0, 0);
    cout << (sum == 0? -1 : sum) << '\n';
}

// -------------------------------------------------------------------

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
//  dp();
    search();
    return 0;
}

例2.Kas

这类题目还有另一种设状态的方法：设 f[i][j] 表示前 i 个数，两人分到的数差值为 j 时两人一共能得到的最大钱数。

转移：

1. 不用第 i 个数：f[i][j]=f[i-1][j]；
2. 把第 i 个数给先手：f[i][j]=f[i-1][j-a[i]]+a[i]；
3. 把第 i 个数给后手：f[i][j]=f[i-1][j+a[i]]\textcolor{red}{+a[i]}。（这里的转移有改动）

注：这道题用之前介绍的状态设计方法也可以。这里是为了演示。

得到答案之后，考虑“赌场”的操作。 两人平均分到 x=\lfloor f[n][0]/2 \rfloor 的钱，剩下 \sum a[i]-x 的钱去赌场，双倍返现，所以两人都分得 \sum a[i] - x 这些钱。

不用担心除不尽，因为题目要求两人拿到的钱数相同，所以 f[n][0] 一定是一个偶数。

注意这道题还要用滚动数组优化。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1005, maxc = 1e5 + 7;

int n, a[maxn], f[2][2 * maxc]; // 开二倍，避免越界
int sum = 0;

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i]; sum += a[i];
    }

    memset(f, -0x3f, sizeof f); // 初始化为极小值
    f[0][0] = 0;
    for(int i = 1; i <= n; i ++){
        for(int j = 0; j <= sum; j ++){
            int x = !(i & 1), y = i & 1;
            f[y][j] = max({f[x][j], f[x][j + a[i]] + a[i], f[x][abs(j - a[i])] + a[i]});
        }
    }
    cout << sum - f[n & 1][0] / 2 << '\n';
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}

例3.小a和uim之大逃离

这道题一看就是差值 dp，不过由线性 dp 被改到了网格上。

先考虑差值 dp 的经典状态：设 f[i][j][d] 表示走到 (i,j)，当前两人取的数差值为 d 时的方案数。

注意到这道题还有一个“最后一步必须由 uim 吸收”的限制，所以考虑再加一维表示取的人：