【题意概述】
现有n个砝码，重量分别为a1，a2，a3，……，an，在去掉m个砝码后，问最多能称量出多少不同的重量（不包括0）。
【题解】
先DFS决定用哪些砝码，然后DP求可以称出的重量有多少种
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 const int maxn=2010; 6 int n,m,a[maxn],b[maxn],ans=0,tot; 7 bool v[maxn],f[maxn]; 8 void read(int &k){ 9 k=0; int f=1; char c=getchar(); 10 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 11 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 12 k*=f; 13 } 14 void dp(){ 15 memset(f,0,sizeof(f)); tot=1; b[1]=0; 16 for (int i=1;i<=n;i++) if(v[i]){ 17 int now=tot; 18 for(int j=1;j<=now;j++) if(!f[b[j]+a[i]]) f[b[j]+a[i]]=1,b[++tot]=b[j]+a[i]; 19 ans=max(ans,tot-1); 20 } 21 } 22 void dfs(int dep,int tot){ 23 if(dep>=n){if(tot>=n-m) dp(); return;} 24 if(tot<n-m) v[dep+1]=1,dfs(dep+1,tot+1),v[dep+1]=0; 25 dfs(dep+1,tot); 26 } 27 int main(){ 28 read(n); read(m); 29 for (int i=1;i<=n;i++) read(a[i]); 30 sort(a+1,a+1+n); dfs(0,0); 31 return printf("%d ",ans),0; 32 }