洛谷题解 P5020 【货币系统】

题目链接

这是一篇85分的题解

思路:

  • 虽然我考场上没有看懂题意,但这并不妨碍我们通过研究样例,发现实际上就是去掉可以被分解为小数的大数。

样例1:

3 19 10 6 去掉6 = 3 * 2,去掉19 = 10 + 6 + 3 。

  • 既然如此我们便将这些数字排序,最小的肯定不能被去掉,我们从第二位开始,依次dfs试图将其用小的数字表示出来。。。

接下来是代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[105],flag; //flag来标记是否已经可以表示
void dfs(int,int);
void dfs(int pos,int sum) //pos:要搜索的数字的下标 ,sum:当前被分解剩余
{
    if(flag)
        return;
    if(sum==0) //被分解完了
    {
        flag=1;
        return;
    }
    for(int i=pos-1;i>=1;i--) //从后往前搜索,减少时间复杂度
    {
        if(sum%a[i]==0) //这个剪枝好像没多大用
        {
            flag=1;
            break;
        }
        if(a[i]<=sum)
            dfs(pos,sum-a[i]);
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(a,0,sizeof a); //初始化!!
        int n;
        cin>>n;
        int m=n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+n+1);
        if(a[1]==1||n==1) //特判
        {
            printf("1\n");
            continue;
        }
        for(int i=2;i<=n;i++) //从第二位开始
        {
            flag=0;
            dfs(i,a[i]);
            if(flag)
                m--;
        }
         cout<<m<<endl;
    }
    return 0;
}

以上