自动搬运

查看原文

来自洛谷，原作者为

	communist Who Dare Wins !

搬运于2025-08-24 21:26:33，当前版本为作者最后更新于2018-05-18 11:53:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到这道题，我们首先注意到“找出其所有的加等式的个数”，自然地考虑运用计数DP求出若干数相加的和的个数

考虑将每个元素排序后DP处理若干数相加的和的个数

用$f[i]$表示

对于一个数$a[i]$，对于前$i-1$个元素选或不选的和$j-a[i]$，选$a[i]$后的和为$j$，则组成$j-a[i]$的方案数会对组成$j$的方案数做出大小为$f[j-a[i]]$的贡献，

所以枚举$i,j$,像这样转移$f[j]+=f[j-a[i]]$

考虑加等式的统计：

对于一个整数集合，我们定义“加等式”如下：集合中的某一个元素可以表示成集合内其他元素之和。

对于一个数，我们已经得到它之前所有数选或不选的和等于它的方案数，为了避免漏记，考虑到对于$i>j$，$i$一定不会作为$j$的加等式中的元素出现，所以我们可以在输入时排序，从小到大DP，对于每个元素$a[i]$，统计它对答案$f[a[i]]$的贡献

上代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int t,m,a[40],f[30010],sum;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>m;
        sum=0;
        for(int i=1;i<=m;i++)
        {
            cin>>a[i];
            sum+=a[i];
        }
        sort(a+1,a+m+1);
        memset(f,0,sizeof(f));
        f[0]=1;
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            ans+=f[a[i]];
            for(int j=sum;j>=a[i];j--)
                f[j]+=f[j-a[i]];
        }
        cout<<ans<<endl;
    }
    return 0;
}