货币系统 （dp/暴力）

题意要求我们构造两个等价的货币系统

我们把已知的货币系统中冗余的删掉
比如有3 6 那么 我么可以删掉6 ，因为6可以用3表示
又比如 19 10 3 那么我们可以删掉19 ，因为19=10+3+3+3

首先说说暴力的解法，因为数据范围比较小，
对于序列中的每一个数字 a[i] 用dfs去判断 能不能用其余的数字去构造出这个a[i]，如果可以 就可以打上标记，然后删掉
这里给出dp 的解法
我们把序列从小到大排序
先把最小的假如背包中，因为最小的无法被其他的表示
然后用 状态转移方程
dp[i]|=dp[i-a[i]]
代码

#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <bitset>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define UpMing main
#define re register
#pragma GCC optimize(2)
#define Accept return 0;
#define lowbit(x) ((x)&(-(x)))
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int inf =0x3f3f3f3f;
const int maxn=1e5+7;
const ll mod = 1e9+7;
const int N =1e6+7;
inline ll read() {
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
void out(ll x) {
    int stackk[20];
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(!x) {
        putchar('0');
        return;
    }
    int top=0;
    while(x) stackk[++top]=x%10,x/=10;
    while(top) putchar(stackk[top--]+'0');
}
ll n,a[maxn],f[maxn],m;
int UpMing() {
    ll otot=read();
    while(otot--) {
        mst(f,0);
        n=read();
        m=n;
        rep(i,1,n) a[i]=read();
        sort(a+1,a+1+n);

        f[0]=1;
        for(int i=1; i<=n ; i++) {
            if(f[a[i]])
                m--;
            else
                for(int j=a[i]; j<=a[n]; j++) f[j]|=f[j-a[i]];

        }
        printf("%lld\n",m);
    }
    Accept;
}

/*

*/