题目描述

货币系统，感觉和整数划分问题很像

该题目的思路为，遍历每个面值，在已有的集合中计算该面值的表示方法有几种

#include <iostream>
#include <cstring>
using namespace std;

const int N=120;
int a[N],b[N],f[30000];


int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(f,0,sizeof f);
        int n;
        cin>>n;
        int m=n;
        int maxa=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            maxa=max(maxa,a[i]);

        }


        for(int i=1;i<=n;i++)
        {
            //注意此处要+=1，表示遍历到一个面值时，该面值的表示方法+1
            f[a[i]]+=1;
            for(int j=maxa;j>=a[i];j--)
            {
                //从最大面值的钱开始遍历，看看该钱能不能被其他钱表示
                //该钱的表示方法=不选第i个面值的钱的方法+选第i个面值的钱的方法
                for(int k=1;k*a[i]<=j;k++)
                f[j]=f[j]+f[j-k*a[i]];
            }
        }
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(f[a[i]]>1)
            cnt++;
            //cout<<a[i]<<endl;
        }

        cout<<m-cnt<<endl;

    }
    return 0;
}

由于是完全背包问题，可以优化成这样：

        for(int i=1;i<=n;i++)
        {
            //注意此处要+=1，表示遍历到一个面值时，该面值的表示方法+1
            f[a[i]]+=1;
            for(int j=a[i];j<=maxa;j++)
            {
                //从最大面值的钱开始遍历，看看该钱能不能被其他钱表示
                //该钱的表示方法=不选第i个面值的钱的方法+选第i个面值的钱的方法
                //for(int k=1;k*a[i]<=j;k++)
                f[j]=f[j]+f[j-a[i]];
            }
        }

2023/11/28

复习了好久，没做出来，可惜
最初的问题是：为集合中的每个数都算了一次它的划分方式(用其他的数表示它), 可是超时了
问题出在：只需要算一次集合中最大值的划分方式，中间所有数的划分方式都会计算好

// 思路：求数组中每个数的数字划分方式，如果>=2(自己表示自己算一种) 则证明它可以被该数组中的其他数表示
// 上面的思路错了。不能为每个数求它的整数划分方式，这样会超时
// 正确思路： 使用集合中的所有数，求集合中最大值的整数划分方式，这样遍历一遍之后所有<=最大值(也就是所有其他数)的整数划分都会被算好

fij: 用集合中前i个数表示，总和恰好为j的表示方法
初始化：f00 = 1

#include <iostream>
#include <cstring>

using namespace std;

int T,n;
const int N=30010;
int f[211][N];
int a[N];

// 思路：求数组中每个数的数字划分方式，如果>=2(自己表示自己算一种) 则证明它可以被该数组中的其他数表示
// 上面的思路错了。不能为每个数求它的整数划分方式，这样会超时
// 正确思路： 使用集合中的所有数，求集合中最大值的整数划分方式，这样遍历一遍之后所有<=最大值(也就是所有其他数)的整数划分都会被算好


int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        memset(f, 0, sizeof(f));
        int maxa = 0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            maxa = max(a[i], maxa);
        }

        // res记录有多少数字的划分方式>=2
        f[0][0] = 1;
        // fij: 用前i个数表示，总和恰好为j的表示方法有几种
        for(int i=1;i<=n;i++)
        {

            for(int j=0;j<=maxa;j++)
            {
                f[i][j] = f[i-1][j];
                if(j >= a[i])
                {
                    f[i][j] += f[i][j-a[i]];
                }

            }
        }

        int res=0;
        for(int i=1;i<=n;i++)
        {
            if(f[n][a[i]] == 1)
            {
                res++;
            }
        }



        cout<<res<<endl;

    }


    return 0;
}