P5020 [NOIP 2018 提高组] 货币系统 · 题解

jcs_pp · 2025-04-11 18:10:01 · 题解

P5020

总体思路：

这题让我们给出一个与原货币系统等价的货币系统，分析题目和样例可发现，这其实就是在优化原货币系统。

如何优化呢？

如果一种货币的面额可以用其他货币表示出来，那么他就没有存在的必要了，就可以优化。 例如：样例的第一组数据，优化了 6 和 19 ，因为 6 可以用 3 表示出来 （6=3+3） ， 19 可以用 3 和 10 表示出来 （19=3+3+3+10）

所以我们就找到那些不可以优化（不可以用其他货币表示出来）的货币即可，即求每种面额能被表示几遍，用动态规划中的完全背包。

上代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int T,n;
int a[110];
int dp[110][25010];
int mx;
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        mx=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            mx=max(mx,a[i]); 
        }
        for(int i=1;i<=n;i++)//基本完全背包 
        {
            dp[i][0]=1;
            for(int j=1;j<=mx;j++)//求到最大面额的货币就好了 
            {
                dp[i][j]=dp[i-1][j];
                if(j>=a[i]) dp[i][j]=dp[i][j]+dp[i][j-a[i]];
            }
        }
        int ans=0; 
        for(int i=1;i<=n;i++)
        {
            if(dp[n][a[i]]==1) ans++;//剩下的货币 
        }
        cout<<ans<<'\n';
    }
    return 0;
}