由一个低级dp错误引发的反思

Author Avatar
MorphLing 9月 30, 2021

昨天训练时有一道并不难的dp题 http://codeforces.com/gym/103202/problem/H

大意是有n种卡，每种卡有d,k,c三个属性，表示有效时间，使用次数和价格，每张卡可以买任意次，也可以不用卡。再给出m天，用$p_i,q_i$表示一个人要在$p_i$天买$q_i$次东西，问最小代价。

解法类似于一个完全背包，按照一个显然正确的策略：只有一张卡次数用完之后才会买下一张卡，用$f[i]$表示完成第$i$次购买后的最小代价，可以得到状态转移式：其中$l(i,k)$表示如果在第i次购买使用了第k种卡，这张卡最早能用于哪次购买。可以发现$l$是有单调性的，即$l(i-1,k)\leqslant l(i,k)$，可以在dp过程中$O(1)$计算。

为了写起来方便，一开始并没有按照状态转移的顺序严格从前往后转移，而是用刷表法往后更新答案，即用$f[i - 1] + c[k]\rightarrow f[i+r(i,k)]$的方式更新，然后在外层循环卡的类型，内层循环购买次数。

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;

const int N = 3e6 + 5;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;
int n, m, r;

struct Buy {
    int p, q;
    bool operator < (Buy &B) const {
        return p < B.p;
    }
}b[N];

int d[N], k[N], c[N], day[N], f[N];

signed main() {
    scanf("%lld %lld %lld", &n, &m, &r);
    for (int i = 1; i <= n; i++) {
        scanf("%lld %lld %lld", &d[i], &k[i], &c[i]);
    }
    for (int i = 1; i <= m; i++) scanf("%lld %lld", &b[i].p, &b[i].q);
    sort(b + 1, b + 1 + m);
    int now = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= b[i].q; j++) {
            day[++now] = b[i].p;
        }
    }
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= now; i++) f[i] = min(f[i], f[i - 1] + r);
    for (int i = 1; i <= n; i++) {
        int tr = 1;
        int dd = d[i], kk = k[i], cc = c[i];
        for (int j = 1; j <= now; j++) {
            while(tr <= now && tr - j <= kk - 1 && day[tr] - day[j] <= dd - 1) tr++;
            tr--;
            f[tr] = min(f[tr], f[j - 1] + cc);
        }

        for (int j = now - 1; j >= 1; j--) f[j] = min(f[j], f[j + 1]);
    }
    printf("%lld\n", f[now]);
    return 0;
}

然后就WA了，且并不觉得写法有什么问题。

为什么在外层枚举卡类型的转移方式是错的

这种写法本质上是一个二维dp，即用$f[i][j]$表示用前i种卡，完成前j次购买的最小花费

其实如果把状态转移写出来就会发现错的很离谱，正确的状态转移是：

然而这种写法就只考虑了一种k==i的情况，也就是

遗漏了某些可能的转移前驱状态，这当然就错了…

一个简单的反例：

1 3 10
1 3 12
1 1
2 3
3 1

即有5次购买，分别发生在1，2，2，2，3天，正确解法是第一天花10块直接买，第二天花12块办卡，第三天花10块直接买，10+10+12=32

然而用上面的解法，第五次购买只考虑了办卡的情况，得到的解是10+12+12=34

为什么错的这么离谱还发现不了

原因1：刷表法在转移关系的表现上不如填表法直观

原因2：类比了背包问题（如完全背包），认为背包问题可以在外层循环物品种类并正确求解，那我在这里外层循环卡的种类应该也是对的

为什么完全背包就能在外层枚举物品

其实我们一直忽略了一个非常重要的前提条件…

就是完全背包问题中，可以任意改变物品加入背包的顺序，那么我就可以假设物品就是按照我在外层枚举的顺序加入的，这并不会对最终解产生影响

或者说我这样求解得到的就是按照特定顺序加入背包这种情况下的最优解，只是恰好这两种解可以互相转换，所以数值相等而已

也就是说这种基本的策略或性质，是会直接影响到dp转移的正确性的

如果我在这题用外层枚举卡类型的方式求解dp，实际上是又加了一个限定条件：“在使用了第i种卡后，就不能再使用编号<i的卡了”，这显然与原问题不等价，所以是错的

而背包问题则是“在使用了第i种物品后，就不能再使用编号<i的物品了”，问题仍然等价，所以是对的

反思

感觉还是要多从状态转移的本质去考虑问题，以前主要在用填表法做dp题，这样先保证不遗漏前驱状态，再考虑更新后继状态，很少用刷表法，一用刷表法就遗漏状态了，说明对状态转移的理解还是比较弱。

dp正确性和某些策略的正确与否是分不开的，所谓不遗漏前驱状态，并不一定要包括广义上（或者说按照题意朴素模拟）的所有前驱状态，而可以是“采用某种策略”的情况下的前驱状态。完全背包之所以可以在外层枚举物品类型就是一个例子。