题目大意
给出一组数，求出其中共有多少数不能被其他数表示
解题思路
法一：可爱的动态规划
这个思路还是比较好想的（也比较好写？）
有依赖关系的背包，思路这道题是差不多的 填满型01背包
（关于代码） 写起来坑还是比较多的，ans,f记得清零，边界记得写就不说了，转移方程那里
f[j] |= f[j - a[i]];
或符号是一定要加的，举个栗子说明：
#include<bits/stdc++.h> using namespace std; const int N = 25050; #define fr(i,n) for(register int i = 1; i <= n; i++) int n,t,m,ans,maxn,a[N],f[N]; int main() { scanf("%d",&t); while(t--){ scanf("%d",&n); fr(i,n) scanf("%d",a + i); sort(a + 1, a + 1 + n); ans = 0; memset(f,0,sizeof(f)); f[0]=1; fr(i,n){ if(f[a[i]]) continue; ans++; f[a[i]] = 1; for(int j = a[i]; j <= a[n]; j++) f[j] |= f[j - a[i]]; } printf("%d\n",ans); } return 0; }
法二：
某种筛（原谅数论全忘光的蒟蒻不知道这是哪种）
实际上和背包思路差不多的……然鹅因为是成倍成倍的筛的所以可能快点？emmm
下面是luogu题解大佬 txtxj 的代码（对我真的懒得打）
#include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int mon[25001]={}; /* mon[i]=0 表示i面值的钱不能被凑出来 mon[i]=1 表示i面值的钱可以被凑出来 mon[i]=2 表示i面值的钱是货币系统中本来就有的钱 */ int coins[101]={};//存钱的面值 int T,n,ans=0; int main() { scanf("%d ",&T); while (T--) { ans=0; memset(mon,0,sizeof(mon)); memset(coins,0,sizeof(coins)); scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&coins[i]); mon[coins[i]]=2; } //把货币系统中的钱标好 sort(coins+1,coins+1+n); for (int i=1;i<=coins[n];i++) { if (mon[i]>0) //如果mon[i]能被凑出来 //那么mon[i+coins[j]]也能被凑出来 { for (int j=1;j<=n;j++) if (i+coins[j]<=coins[n]) //防止数组越界 mon[i+coins[j]]=1; else break; } } for (int i=1;i<=coins[n];i++) if (mon[i]==2) ans++; printf("%d\n",ans); } }