题目:POJ1742

大意:有n种不同大小的硬币,面值是ai每种有mi个,题目问,这些硬币能够在价格1-m之间,付款多少种金额?

这个问题就是dp的多重部分和问题,在定义递推关系的时候,不同的递推关系会影响到复杂度。

下面是TLE的思路:

dp[i+1][j]=前i种数字能否加成j

那么,递推关系就是dp[i+1][j]=(0<=k<=mi且k*ai<=j时存在使dp[i][j-k*ai]为真的k) 其实这就是把他们 或 起来

然而这个算法的复杂度是O(KΣimi),于是在题目要求下,就tle了

下面是MLE的思路

如果我们不仅求出是否能加和得到目标数值,还顺便把得到这个数的时候,ai还剩下多少个也算出来,那么就可以降低时间复杂度。

把dp数组改为:

dp[i+1][j]=用前i种数,加和得到j时,第i种数最多还能剩下多少个。

按照上面的递推关系,写出转移方程:

  1. dp[i+1][j]= mi (dp[i][j]>=0) 就是说,当前i-1种数已经可以加和为j了,那么第i种数就不需要加了,最多还能剩下mi个。
  2. dp[i+1][j] = -1 (当不属于上面的情况时,若j<ai或者dp[i+1][j-ai]<=0) 也就是说,当j比第i种数的大小还小的话,就没法通过加上ai得到j,因此设置为-1.并且,当j-ai小于等于0的时候,说明当前数已经用完了,没法加到j了。
  3. 除了上面两种情况以外,则dp[i+1][j]=dp[i+1][j-ai]-1 也就是从前i种数加到j-ai转移而来。

上面这个思路是正确的,但是我们需要开一个很大的二维数组,对于这一题来说,就MLE了

重复利用数组,降低空间复杂度

我们会发现,当我们进行循环时,是按照i,一位一位进行增加的,在计算第i位的时候,i-1位之前的数据其实已经不需要了。我们新生成的第i位的数据仅仅是由第i-1位转移而来的,并且,一旦完成转移,第i-1位的数据也不再需要了。这样的话,我们可以只用一个数组来记录。

因此,AC代码如下:

#include <iostream>
using namespace std;
#define MAXN 105
#define MAXM 100005
struct coin
{
    int val, num;
} c[MAXN];
int n, m;

int dp[MAXM]; //前i种硬币,加到j元时,第i种剩余的最大值

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    while (1)
    {
        cin >> n >> m;
        if (n == 0 && m == 0)
            break;

        for (int i = 0; i < n; ++i)
        {
            cin >> c[i].val;
        }
        for (int i = 0; i < n; ++i)
        {
            cin >> c[i].num;
        }

        for (int i = 0; i <= m + 1; ++i)
        {

            dp[i] = -1;
        }
        dp[0] = 0;


        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j <= m; ++j)
            {
                if (dp[j] >= 0)
                    dp[j] = c[i].num; //前i-1种硬币已经能加到j元
                else if (j < c[i].val || dp[j - c[i].val] <= 0)
                {
                    //前i种硬币无法加到j元
                    dp[j] = -1;
                }
                else
                {
                    dp[j] = dp[j - c[i].val] - 1;
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= m; ++i)
        {
            if (dp[i] >= 0)
                ++ans;
        }
        cout << ans << endl;
    }
    return 0;
}

转载请注明来源:https://www.longjin666.top/?p=1099

你也可能喜欢

发表评论