砝码称重

发表于 更新于 分类于 阅读次数：

Luogu P1441 砝码称重 在N个数中去掉M个数，剩下的取任意个数相加，求最多能得到多少种和 看到题解里有用位运算的，不过本题dfs+dp即可解决 首先dfs出所有去掉M个数后的情况，暴力枚举即可

1
2
3
4
5
6
7
8
9
10
11
12
// s表示选中数字最大和
void dfs(int n, int m, int s)
{
    if(n + m > N + 1) return;
    if(m == 0) dp(s);
    else {
        dfs(n + 1, m, s);
        use[n] = false;
        dfs(n + 1, m - 1, s - a[n]);
        use[n] = true;
    }
}

由数据范围可知，本题的和最大不超过2000，容易想到dp求和的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dp(int s)
{
    memset(f,0,sizeof(f));
    f[0]=true;
    for (int i = 1; i <= N; ++i) {
        if (!use[i]) continue;
        for (int j = s; j >= a[i]; --j){
            f[j] = f[j-a[i]];
        }
    }
    int cnt = 0;
    for(int i = 1; i <= s; ++i){
        cnt += f[i];
    }
    ans = max(ans, cnt);
}