WOJ 46 完全背包

高级的暴力，神仙优化……

首先$O(n^{3})$的$dp$很好想，然后这样可以$O(1)$地回答询问。

考虑到所有物品的体积是一个连续的区间，所以说我们可以合并一些物品来达到预处理时间均摊的效果。

我们知道$k = pm + q$表示一个带余除法，那么我们对于每一个$k$，考虑枚举物品的体积$v$然后选取一个适当的模数$m$来优化计算。

对于每一个询问$ans = max(f_{pm, i}, f_{q, v - i}) ( 0 \leq i \leq v)$

这样的话我们预处理$f_{0,1,2,...,m}$和$f_{m, 2m, 3m, ..., km} (n \leq km)$就可以回答问题了。

根据分块的思想当$m = \sqrt{n}$时，合并后的物品的数量是根号级别的，这样预处理的时间复杂度是$O(n ^ {2.5})$较优，回答每一个询问的时间是$O(n)$，可以通过本题。

还有一个小细节就是要注意当$q$取1时其实答案只能取$f_{q, v}$，但是找答案的过程中可能会出现$f_{q, i} (i < v)$比答案大的情况，所以我们将$f$先全部标记为不合法状态，然后记$f_{0, 0} = 0$为合法状态，就可以避免中间项答案的干扰。

膜Claris。

Code：

#include <cstdio>

#include <cmath>

#include <cstring>

using namespace std;

const int N = ;

const int M = ;

const int inf =  << ;

int n, m, qn, w[N], f[M][N], g[M][N];

inline void read(int &X) {

    X = ;

    char ch = ;

    int op = ;

    for(; ch > ''|| ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

inline void chkMax(int &x, int y) {

    if(y > x) x = y;

}

int main() {

    memset(f, , sizeof(f));

    memset(g, , sizeof(g));   

    read(n), read(qn);

    m = sqrt(n) + ;

    for(int i = ; i <= n; i++) {

        read(w[i]);

        f[][i] = w[i];

    }

    for(int i = ; i <= m; i++)

        for(int j = ; j <= n; j++)

            for(int k = ; k <= j; k++)

                chkMax(f[i][j], f[i - ][k] + w[j - k]);

    g[][] = f[][] = ;

    for(int i = ; i <= n; i++)

        g[][i] = f[m][i];

    for(int i = ; i <= m; i++)

        for(int j = ; j <= n; j++)

            for(int k = ; k <= j; k++)

                chkMax(g[i][j], g[i - ][k] + f[m][j - k]);

    for(int k, v, a, b, ans; qn--; ) {

        read(k), read(v);

        ans = -inf, a = k / m, b = k % m;

        for(int i = ; i <= v; i++)

            chkMax(ans, f[b][i] + g[a][v - i]);

        printf("%d\n", ans);

    }

    return ;

}

巴特西

WOJ 46 完全背包

最新文章

热门文章