自动搬运

查看原文

来自洛谷，原作者为

	ZM____ML 也许是 因上帝与人类都生来寂寞,于是 我们相遇了

搬运于2025-08-24 22:45:22，当前版本为作者最后更新于2023-06-07 22:35:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

比较明显的一道动态规划题。

定义状态 $dp_{i,j}$ 表示前 $i$ 个数能够表达 $1\sim j$ 之间所有的数字，那么我们可以看出，$dp_{i,j}$ 可以从两个状态转移过来：

1. $dp_{i-1,j}$ 不选第 $i$ 个数字。

2. $dp_{i-1,j-a_i}$ 选第 $i$ 个数字。

跟背包的形式很像，因为都是从 $i-1$ 转移过来的，所以说这一维可以滚掉。

为了方便判断，我们把数组排一下序，保证如果当前状态加上 $a_i$ 大于总数之后，那么加上后面的任意一个数都会大于总数。

注意：转移时需要保证 $a_i\le j+1$。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5e3+5,mod=1e9+7;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return x*f;
}
int n,a[N],f[N],ans;
signed main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	sort(a+1,a+n+1);
	f[0]=1;
	for(int i=1;i<=n;i++)
		for(int j=N-5;j>=a[i]-1;j--)
			f[min(j+a[i],N-5)]+=f[j],f[min(j+a[i],N-5)]%=mod;
	for(int i=1;i<=N-5;i++)ans=(ans+f[i])%mod;
	printf("%d",ans);
	return 0;
}