T137226 彩虹海
設目標體系$(n,a)$和答案體系$(m,b)$分別為集合$A$和集合$B$，那么我們可以猜想$B\subseteq A$。
我們可以先通過反證法驗證下面兩個結論：
若$x\in A$可以被其他$A$中的數表達出來，那么有$x\notin B$。
若$x\in A$不能被其他$A$中的數表達出來，那么有$x\in B$。
然后再通過上述結論，使用反證法證明$B\subseteq A$。具體就是取一個$x$，令$x\in B$且$x\notin A$，證明這樣的$x$不存在。
于是我們只需要找到$A$中能被表達出來的數并刪去即可。
具體來說，需要先將$a$排序，然后每次$\forall x\in[a_i,a_n]$，令$f_x\leftarrow f_{x-a_i}$。
代碼：
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define IL inline #define RG register using namespace std; #define RI RG int #define RC RG char const int N=100; const int M=25000; int T,n,a[N+3]; bool f[M+3]; IL void sol(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); memset(f,0,sizeof(f)); f[0]=1; int ans=n; for(RI i=1;i<=n;i++){ if(f[a[i]]){ ans--; continue; } for(int j=a[i];j<=a[n];j++) f[j]|=f[j-a[i]]; } printf("%d\n",ans); } int main(){ freopen("data.in","r",stdin); freopen("data.ans","w",stdout); scanf("%d",&T); while(T--) sol(); return 0; }
浙公網安備 33010602011771號