532. 货币系统(bool型完全背包，贪心)

 原题链接

分析：

对于两个等价的货币系统来说，有以下限制条件

对于任意一个非负整数x，要么都可以表示，要么都不可以表示

于是可以得出引理，对于两个等价的集合A,B(B表示被简化的系统)

A集合中不能被A中其他元素凑出来的数，一定会出现在B集合中A集合中能被A中其他元素凑出来的数，一定不会出现在B集合中

引理1证明：

A集合与B集合等价的条件是凑出的数相同，不能凑出的数也相同

反证：假如B集合中存在一个不在A集合中且不能被A集合表示出来的数，那么这个数就不能被A集合表示出来，凑不出来，由于B集合和A集合等价，可以清楚这种方案是不会存在的

引理2证明：

A集合中能被A中其他元素凑出来的数，一定不会出现在B集合中

由于B集合是一个最简的集合，根据贪心的策略，如果他能被凑出来，那他对于凑出其他新的数没有贡献，却多占了一个位置，应该剔除

结论：

一个最简系统B必然是由A中的元素表示出来的

初始化：dp[0]=true

状态表示：考虑前i个数，数字j能否被凑出

状态计算：根据最后一个不同点，即最后一次选择a[i]几次，可以划分为多个子集

当前选了0次                        dp[i,j]=dp[i-1,j]当前选了1次                        dp[i,j]=dp[i-1,j-a[i]]...

#include 
#include 
#include 
using namespace std;
const int N=25010;
const int M=105;
bool dp[N];
int a[N];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(dp,0,sizeof dp);
        int n;
        cin>>n;
        for(int i=0;i>a[i];
        sort(a,a+n);
        int m=a[n-1];
        dp[0]=true;
        int res=0;
        for(int i=0;i