【题解】HEOI2013Eden 的新背包问题

　　这题真的神奇了……蜜汁复杂度(｀・ω・´)

　　应该是一个比较连贯的思维方式：去掉一个物品，那么我们转移的时候不考虑它就好了呗。考虑暴力：每一次都对剩余的n - 1个物品进行多重背包转移，获得答案。既然可以优化，就说明一定有重复计算的地方——画出一张方格图，把不需要的格子涂掉——我们突然发现每一个可以有两部分组成，而两部分可以递推得到！那就很简单了：A[i][]表示选择n ~ i 这些物品能获得的最大值，B[i][]表示选择1~i的物品所能获得的最大值。

　　答案就是两部分的AB数组暴力合并即可。

#include<bits/stdc++.h>

using namespace std;

#define maxn 1500

#define maxq 300015

int n, q, W[maxn], V[maxn], w[maxn * ], v[maxn * ], T[maxn];

int cnt, L[maxn], R[maxn], A[maxn][maxn], B[maxn][maxn];

int M;

struct que

{

    int num, id, m;

}Q[maxq];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

void Get_A()

{

    for(int i = n; i >= ; i --)

    {

        int s = T[i], t = ;

        L[i] = cnt + ;

        while(s >= t)

        {

            w[++ cnt] = W[i] * t;

            v[cnt] = V[i] * t;

            s -= t, t *= ;

        }

        if(s)

        {

            w[++ cnt] = W[i] * s;

            v[cnt] = V[i] * s;

            s -= t, t *= ;

        }

        R[i] = cnt;

        memcpy(A[i], A[i + ], sizeof(A[i + ]));

        for(int j = L[i]; j <= R[i]; j ++)

            for(int k = M; k >= w[j]; k --)

                A[i][k] = max(A[i][k], A[i][k - w[j]] + v[j]);

    }

}

void Get_B()

{

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

    {

        memcpy(B[i], B[i - ], sizeof(B[i - ]));

        for(int j = L[i]; j <= R[i]; j ++)

            for(int k = M; k >= w[j]; k --)

                B[i][k] = max(B[i][k], B[i][k - w[j]] + v[j]);

    }

}

int main()

{

    n = read();

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

        W[i] = read(), V[i] = read(), T[i] = read();

    q = read();

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

    {

        Q[i].num = read() + , Q[i].m = read();

        Q[i].id = i;

        M = max(Q[i].m, M);

    }

    Get_A();

    Get_B();

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

    {

        int k1 = Q[i].num + , k2 = Q[i].num - ;

        int j = Q[i].m, ans = ;

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

            ans = max(ans, A[k1][a1] + B[k2][j - a1]);

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

    }

    return ;

}

巴特西

【题解】HEOI2013Eden 的新背包问题

最新文章

热门文章