题解：P5020 [NOIP2018 提高组] 货币系统

Laoda_Bryant · 2024-12-30 18:49:19 · 题解

运用算法：贪心和完全背包。

思路

首先直接求 (m,b) 是比较困难的。所以先考虑从 (n,a) 中减去一些多余的面额。
那什么面额是多余的呢，当一个数值 a_i 能被比它小的面额表示时，那么它的存在就没有意义了。
那么有没有 k \in (m,b) 并且 k \notin (n,a) 呢，有两种情况：

所以，根据以上推论，我们可以得到 (m,b)\in (n,a)。则我们可以在 a 上做一次完全背包，时间复杂度可以通过本题。

AC code

#include<bits/stdc++.h>
using namespace std;
int a[105],dp[25005],n,T;
int solve(int a[],int n){
    int ans=n;
    sort(a+1,a+n+1);
    int p=1;
    for(int i=1;i<=a[n];i++) dp[i]=0;
    for(int i=1;i<=a[n];i++){
        for(int j=1;a[j]<i;j++){
            if(dp[i-a[j]]) dp[i]=1;
        }
        if(dp[i]==0){
            if(i==a[p]) ++p,dp[i]=1;
        }else if(i==a[p]) ++p,--ans;
    }
    return ans;
}
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        cout<<solve(a,n)<<endl;
    }
    return 0;
}