P1441 砝码称重

题目描述

现有n个砝码，重量分别为a1，a2，a3，……，an，在去掉m个砝码后，问最多能称量出多少不同的重量（不包括0）。

输入输出格式

输入格式：

输入文件weight.in的第1行为有两个整数n和m，用空格分隔

第2行有n个正整数a1，a2，a3，……，an，表示每个砝码的重量。

输出格式：

输出文件weight.out仅包括1个整数，为最多能称量出的重量。

输入输出样例

输入样例#1： 

3 1
1 2 2

输出样例#1： 

3

说明

【样例说明】

在去掉一个重量为2的砝码后，能称量出1，2，3共3种重量。

【数据规模】

对于20%的数据，m=0；

对于50%的数据，m≤1；

对于50%的数据，n≤10；

对于100%的数据，n≤20，m≤4，m＜n，ai≤100。

Solution：

　　本题比较水，先搜索处理出删走$m$个砝码后的情况，再在剩下的$n-m$个砝码中跑$01$背包，处理出能秤出的重量，更新$ans$就$OK$了。

代码：

#include<bits/stdc++.h>
#define il inline
#define ll long long
#define Max(a,b) (a)>(b)?(a):(b)
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=105;
int n,m,f[N*16],a[N],ans,sum;
bool vis[N];
il void solve(){
    sum=0;memset(f,0,sizeof(f));
    f[0]=1;
    For(i,1,n)
    if(!vis[i])Bor(j,a[i],1600)
        if(f[j-a[i]]&&!f[j])sum++,f[j]=1;
    ans=Max(ans,sum);
}
il void dfs(int s,int k){
    if(!s){solve();return;}
    For(i,k,n) if(!vis[i])vis[i]=1,dfs(s-1,i),vis[i]=0;
}
int main(){
    cin>>n>>m;
    For(i,1,n)cin>>a[i];
    dfs(m,1);
    cout<<ans;
    return 0;
}