https://codeforces.com/contest/1807/problem/G1
easy -version 同《货币系统》
背包
f[ j ] 每个数字合成的次数
#include <iostream> #include <cstring> using namespace std ; const int M=5006,N=5006; int n,a[N],cnt[M],f[M]; bool solve(){ int i,j; memset(cnt,0,sizeof cnt) ; cin>>n; for(i=1;i<=n;i++) cin>>a[i],cnt[a[i]]++; if(n==1){ if(a[1]==1) return 1;return 0; } memset(f,0,sizeof f); f[0]=1; for(i=1;i<=n;i++) for(j=5000;j>=a[i];j--) f[j]+=f[j-a[i]]; for(i=1;i<=n;i++) if((f[a[i]]==cnt[a[i]])&&a[i]!=1) return 0; return 1; } signed main(){ int cas; cin>>cas; while(cas--){ if(solve()) cout<<"YES";else cout<<"NO"; cout<<endl; } }
标签:1807,cnt,int,memset,CF,cas,sizeof From: https://www.cnblogs.com/towboa/p/17286420.html