自动搬运

查看原文

来自洛谷，原作者为

	OIer_ACMer El pueblo unido jamás será vencido!

搬运于2025-08-24 23:03:04，当前版本为作者最后更新于2024-08-25 22:41:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目解析：

首先，为啥这道题只有一个点？

好，回归正题，我们首先可以知道这道题是一道多重背包动态规划，于是，我们直接通过板子敲一个多重背包，第一层枚举第几个物品，第二层枚举物品数量多少，最后一层枚举背包容量，最终，若 $dp_i$ 的值不为 $0$，则进行计算，代码如下（我还指望着三层循环能过）：

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1000009], c[1000009];
int dp[1000009];
int main()
{
    while (1)
    {
        cin >> n >> m;
        if (n == 0 && m == 0)
        {
            return 0;
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> c[i];
        }
        for (int i = 1; i <= m; i++)
        {
            dp[i] = 0;
        }
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= c[i]; j++)
            {
                for (int k = m; k >= a[i]; k--)
                {
                    if (dp[k - a[i]])
                    {
                        dp[k] = 1;
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; i++)
        {
            if (dp[i])
            {
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

不是意外地超时了，这时，我们根据方程式中 $dp_k$ 要存在的要求是 $dp_{k - a[i]}$ 以及 $dp_{k - j *a_i}$ 之类的减去新增钱数的状态存在才能符合条件，很明显，这就是动态规划的整体考虑思想。

那么，我们可以根据这一点用数组 $g_j$ 存储 $j$ 状态下有多少种状态，每次在计算时，我们先在 $g$ 数组中找 $g_{j - a_i}$ 的代价是否比 $c_i$ 小，也就是此时能否进行转移，减去一维的枚举，优化了时间复杂度。

正解代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1000009], c[1000009];
int dp[1000009], g[1000009];
int main()
{
    while (1)
    {
        cin >> n >> m;
        if (n == 0 && m == 0)
        {
            return 0;
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> c[i];
        }
        for (int i = 1; i <= m; i++)
        {
            dp[i] = 0;
        }
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            // for (int j = 1; j <= c[i]; j++)
            // {
            //     for (int k = m; k >= a[i]; k--)
            //     {
            //         if (dp[k - a[i]])
            //         {
            //             dp[k] = 1;
            //         }
            //     }
            // }
            for (int j = 0; j <= m; j++)
            {
                g[j] = 0;
            }
            for (int j = a[i]; j <= m; j++)
            {
                if (!dp[j] && dp[j - a[i]] && g[j - a[i]] < c[i])
                {
                    dp[j] = 1;
                    // g[j]++;
                    g[j] = g[j - a[i]] + 1;
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= m; i++)
        {
            if (dp[i])
            {
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}