洛谷P5020 [NOIP2018 提高組] 貨币系統 題解

題目連結：P5020 [NOIP2018 提高組] 貨币系統

題意：在網友的國度中共有 n n n 種不同面額的貨币，第 i i i 種貨币的面額為 a [ i ] a[i] a[i]，你可以假設每一種貨币都有無窮多張。為了友善，我們把貨币種數為 n n n 、面額數組為 a [ 1.. n ] a[1..n] a[1..n] 的貨币系統記作 ( n , a ) (n,a) (n,a) 。

在一個完善的貨币系統中，每一個非負整數的金額 x x x 都應該可以被表示出，即對每一個非負整數 x x x ，都存在 n n n 個非負整數 t [ i ] t[i] t[i] 滿足 a [ i ] × t [ i ] a[i] \times t[i] a[i]×t[i] 的和為 x x x 。然而， 在網友的國度中，貨币系統可能是不完善的，即可能存在金額 x x x 不能被該貨币系統表示出。例如在貨币系統 n = 3 , a = [ 2 , 5 , 9 ] n=3 ,a=[2,5,9] n=3,a=[2,5,9] 中，金額 1 , 3 1,3 1,3 就無法被表示出來。

兩個貨币系統 ( n , a ) (n,a) (n,a) 和 ( m , b ) (m,b) (m,b) 是等價的，當且僅當對于任意非負整數 x x x ，它要麼均可以被兩個貨币系統表出，要麼不能被其中任何一個表出。

現在網友們打算簡化一下貨币系統。他們希望找到一個貨币系統 ( m , b ) (m,b) (m,b) ，滿足 ( m , b ) (m,b) (m,b) 與原來的貨币系統 ( n , a ) (n,a) (n,a) 等價，且 m m m 盡可能的小。他們希望你來協助完成這個艱巨的任務：找到最小的 m m m 。

輸入輸出樣例

輸入 #1

2 
4 
3 19 10 6 
5 
11 29 13 19 17 
           

輸出 #1

2   
5  
           

觀察第一組資料，可以發現其等價于

3 10

因為 19 19 19 和 6 6 6 均可以用 3 3 3 和 10 10 10 替代

而第二組，每一種都是有價值的，不可替代

考慮 d p dp dp ，

設 d p [ i ] dp[i] dp[i] 表示湊出 i i i 最多需要花費的金額種類

顯然這個是個完全背包。

d p [ a [ i ] ] = 1 dp[a[i]]=1 dp[a[i]]=1 則說明 a [ i ] a[i] a[i] 是有價值的面額

然後就沒了，代碼：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(3e4+15)
int Q,n,mx;
int a[115],dp[N];
signed main()
{
    read(Q);
    while(Q--)
    {
        memset(dp,0xc0,sizeof(dp));
        read(n);dp[0]=0;mx=-INF;
        for(int i=1; i<=n; i++)
        {
            read(a[i]);
            mx=max(mx,a[i]);
        }
        for(int i=1; i<=n; i++)
            for(int j=a[i]; j<=mx; j++)
                dp[j]=max(dp[j],dp[j-a[i]]+1);
        int res=0;
        for(int i=1; i<=n; i++)
            if(dp[a[i]]==1)++res;
        write(res);pc('\n');
    }
    return 0;
}
           

其實這個 b b b 是可以證明有 $b \subseteq a $ 的

但是，OI不需要嚴謹證明。OI靠得是OI直覺。

轉載請說明出處