NC11169E

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

Solution

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

表示前 个数满足:

1. 
2. 
   对于 这一维，我们可以对 的数取 不影响答案，这样就得到了一个 的做法。

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

表示前 个数满足:

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

1. 单调递增的同时 单调递增
2. 

在 的条件下求

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

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;
}