题解：CF1032E The Unbearable Lightness of Weights

· · 题解

题意

翻译给的很明确了机翻看了半天才看懂。

思路

因为机翻看了半天，所以把样例搞懂了\ 我们首先观察样例，在样例解释中告诉了第一组样例的选择方法。

我们可以首先发现两件事情：

  1. 对于一种可行的选法，选择它的补集也是可以的。这一点样例解释一说过了。
  2. 所有可能的选法都是只选同一种数字或者其补集。

对于第二个发现：

我们假设有一个可行的方案，它里面包含了两种数，那么我们在得到这个集合后并不能将这两种数对应的砝码区分开。因此这个方案中只能包含一个数。

我们接下来考虑对于什么样的一组方案，它能成为解。我们发现一个方案能成为解，当且仅当这些数的和 m 和个数 k 相同的只有这一种方案（数值相同的算一种）。

那么好了，我们的约束都已经出来了，发现数据范围都 \leq 100 果断用背包，在多一维当个数 k。因为数值相同的算作同一种方案，因此使用分组背包即可。

此外，还需要特判当不同数字的种类数小于两种的时候，我们直接输出 n 即可，因为我们选出一种数，它们的补集我们也就唯一确定了。

code

#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,z,y) for(int x=z;x>=y;x--)
#define TF(x,y,z) for(int x=head[y],z;x;x=nex[x])

using namespace std;

typedef long long ll;
typedef double dou;
typedef const int ci;
typedef pair<int,int> pii;

ci maxn=2e4+10;

int n,a[maxn],cnt[maxn],sum,dp[maxn][110],ans,tot;
int main()
{
    scanf("%d",&n);
    _F(i,1,n)
        scanf("%d",&a[i]),cnt[a[i]]++,sum+=a[i];
    dp[0][0]=1;
    _F(i,1,100)
    {
        if(!cnt[i]) continue;
        tot++;
        F_(j,10000,1)
        {
            F_(k,n,1)
            {
                _F(l,1,cnt[i])
                {
                    if(j<i*l)
                        break;
                    dp[j][k]+=dp[j-i*l][k-l];
                }
            }
        }
    }
    if(tot==2)
    {
        printf("%d",n);
        return 0;
    }
    _F(i,1,100)
    {
        while(dp[i*cnt[i]][cnt[i]]!=1)
            cnt[i]--;
        ans=max(ans,cnt[i]);
    }
    printf("%d",ans);
    return 0;
}

建议降蓝（大雾