[THUPC2017] 钦妹的玩具商店 题解

· · 题解

思路分析

暴力 DP 卡过。

设 DP 数组 f_{i, j} 表示考虑前 i 个玩具，花的钱限制在 j 元以内，能够达到的最大愉悦度；g_{i, j} 则表示考虑后 i 个玩具，其他与 f 相同。

转移直接使用多重背包二进制优化即可。具体见代码。

题目还有 [l, r] 之间的玩具不能取的限制，可以枚举对于 1 \sim l - 1 以及 r + 1 \sim n 两部分分别用的钱（记为 i 和 j），然后直接计算 f_{l - 1, i} + g_{r + 1, j}。

对于相同的 i + j，总钱数是一样的，根据题目“第 i 个小朋友每天都会带 i 元”，i + j 元对应的一定是第 i + j 个小朋友。用数组 mx 记录每个小朋友的最大愉悦度，每次更新取 \max 即可。最后就可以直接用 mx 数组计算出答案了。

注意 不要随意将 DP 数组进行空间优化，压缩成一维。因为这样就无法处理之后的 [l, r] 限制了。

时间复杂度：DP 时用二进制优化，为 \Theta (nm \log t)；但瓶颈在于处理询问限制时要枚举的 i, j，为 \Theta (qm ^2 )。这都能过，你谷评测机是真的强。

代码

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1010, mod = 1e8 + 7;

int c[N], v[N];
vector<PII> a[N];
int f[N][N], g[N][N];
int mx[N];

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        int n, m, q;
        scanf("%d%d%d", &n, &m, &q);
        for (int i = 1; i <= n; i ++ ) a[i].clear();
        memset(f, 0, sizeof f);
        memset(g, 0, sizeof g);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);
        for (int i = 1; i <= n; i ++ ) scanf("%d", &v[i]);
        for (int i = 1; i <= n; i ++ )
        {
            int t;
            scanf("%d", &t);
            int now = 1;
            while (now <= t)
            {
                a[i].push_back({c[i] * now, v[i] * now});
                t -= now, now *= 2;
            }
            if (t) a[i].push_back({c[i] * t, v[i] * t});
        }
        for (int i = 1; i <= n; i ++ )
        {
            for (int j = m; ~j; j -- ) f[i][j] = f[i - 1][j];
            for (auto j : a[i])
                for (int k = m; k >= j.first; k -- )
                    f[i][k] = max(f[i][k], f[i][k - j.first] + j.second);
        }
        for (int i = n; i; i -- )
        {
            for (int j = m; ~j; j -- ) g[i][j] = g[i + 1][j];
            for (auto j : a[i])
                for (int k = m; k >= j.first; k -- )
                    g[i][k] = max(g[i][k], g[i][k - j.first] + j.second);
        }
        int pre = 0;
        while (q -- )
        {
            memset(mx, 0, sizeof mx);
            int x, y;
            scanf("%d%d", &x, &y);
            int l = min((x + pre - 1) % n + 1, (y + pre - 1) % n + 1);
            int r = max((x + pre - 1) % n + 1, (y + pre - 1) % n + 1);
            for (int i = 0; i <= m; i ++ )
                for (int j = 0; i + j <= m; j ++ )
                    mx[i + j] = max(mx[i + j], f[l - 1][i] + g[r + 1][j]);
            int sum = 0, xorsum = 0;
            for (int i = 1; i <= m; i ++ )
            {
                sum = (sum + mx[i]) % mod;
                xorsum ^= mx[i];
            }
            printf("%d %d\n", sum, xorsum);
            pre = sum;
        }
    }
    return 0;
}