NC11169E_牛客博客

比赛的时候写了个假算法，跑的贼快还AC了，现在看了下确实相当不妥，当时写的两个dp并不同步，运气好，数据刚好没有能卡的罢了，现在来补一下正解。

Solution

遇到问题毫无头绪的时候先从暴力的方法入手然后逐步优化。
首先能想到01背包的暴力解法。

$f_{i, j, k}$ 表示前 $i$ 个数满足:

$\sum_{p = 1}^{i}a_p*x_p = j$
$\sum_{p = 1}^{i}b_p*x_p = k$
对于 $k$ 这一维，我们可以对 $\ge P$ 的数取 $P$ 不影响答案，这样就得到了一个 $O(n * P * P)$ 的做法。

现在该思考的是如何优化，注意数据范围: $a_i <= b_i$ 。
这里要用到单调队列优化DP。

$f_{i, j}$ 表示前 $i$ 个数满足:

$\sum_{p = 1}^{i}a_p*x_p \le j$
$\sum_{p = 1}^{i}b_p*x_p \ge j$

单调队列维护一个队列满足：

$k$ 单调递增的同时 $f_k$ 单调递增
$k + b_i \ge j$

在 $b_i + k \ge j$ 的条件下求 $f_{i, j} = min_{k = j-a_i} ^ {j}f_{i - 1, k} + c_i$

对于空间上的优化，我们发现只会用到 $i$ 的状态和 $i - 1$ 的状态，这里可以用滚动数组处理。

Code

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define lowbit(x) ((x) & -(x))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll mod = 1e9 + 7;
constexpr ll N = 1e6 + 5;

int n, P, a[N], b[N], c[N], q[N], head, tail;

void solve() {
    cin >> n >> P;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    const int mx = 2000000005;
    vector<int> f(P + 1, mx);
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        vector<int> g(P + 1, mx);
        head = 1, tail =0;
        for (int j = a[i]; j <= P; j++) {
            if (head <= tail && q[head] + b[i] < j) ++head;
            while (head <= tail && f[q[tail]] >= f[j - a[i]]) --tail;
            q[++tail] = j - a[i];
            if (f[q[head]] != mx) g[j] = f[q[head]] + c[i];
        }
        for (int j = a[i]; j <= P; j++) f[j] = min(f[j], g[j]);
    }
    if (f[P] == mx) {
        cout << "IMPOSSIBLE!!!\n";
    } else {
        cout << f[P] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}