自动搬运

查看原文

来自洛谷，原作者为

	Qutam 额

搬运于2025-08-24 21:25:24，当前版本为作者最后更新于2020-02-16 09:22:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这题是一个背包板子。

对于只选前$i$项的数，它们的和正好是$j$的方案总数，我们可以这样想，先考虑第$i$个数选不选。所以方案总数就应该是选的方案和不选的方案之和。

状态转移方程为：

需要注意，有解的前提必须是数字之和是偶数。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[40],dp[45][2010];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		a[i]=i;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n*(n+1)/2;j++){
			dp[i][j]=dp[i-1][j];
			if(j>=a[i])dp[i][j]+=dp[i-1][j-a[i]];
		}
	if(n*(n+1)%4==0)cout<<dp[n][n*(n+1)/4]<<endl;
	else cout<<0<<endl;
	return 0;
}