题解：P10973 Coins

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