2018.8.21 2018暑假集训之货币系统

恢复

---

试题描述

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。样例：设n=3，m=10，要求输入和输出的格式如下：

输入

第一行包含两个数，分别是n（n<=15）和m(m<=3000) 以下n行每行包含一个数，表示每种货币的面值

输出

输出总的方案数

输入示例

3  10                                //3种面值组成面值为10的方案

1                                      //面值1

2                                      //面值2

5                                      //面值5

输出示例

10

---

多么古老的一道题有木有？

然而这个题向我们说明了古人也是很坑的

先看数据范围搜索可能会TLE

考虑dp/递推

其实思路很好想

和以前一样 考虑不同的变量 不难发现状态之间可以用一张不同面值的货币转移

比如我们用dp[i]表示取到面值为i有多少种取法

那么dp[i]=dp[i]+dp[i-money[j]]

多么简单有没有？？？

先上一波代码

#include<iostream>
using namespace std;
int dp[10050],money[10050],n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&money[i]);
    dp[0]=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(money[j]>i)continue;
            dp[i]+=dp[i-money[j]];
        }
    }
    printf("%d",dp[m]);
    return 0;
}

然而这样明显是有问题的
经过调试我们可以发现从dp[3]的取值开始就出现错误

dp[3]应该等于2而不是等于3

不难发现是因为dp[3]将1 2和2 1算作了两种

那么问题来了

怎么办？？

还记得01背包和floyd的循环吗

之所以外面要先循环物品和节点

就是为了避免出现序列上的重复

比如说对于这个题来讲

如果最外层控制物品就可以让每个重量先装物品1、再装物品2

比如dp[3]在转移到dp[3-1]时dp[2]=1

因为此时装成2的方法只有1 1！！

这就是为什么可以避免出现上面的情况

上代码

#include<iostream>
using namespace std;
int dp[10050],money[10050],n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&money[i]);
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=money[i];j<=m;j++)
        {
            dp[j]+=dp[j-money[i]];
        }
    }
    printf("%d",dp[m]);
    return 0;
}

有点太坑人了吧qwq