自动搬运

查看原文

来自洛谷，原作者为

	UnyieldingTrilobite 直到世界 只剩下闪烁的黑白

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

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

以下是正文

Update:2020.2.28,修复错别字，麻烦管理员重新过下！

好像只有一篇过不了样例的题解。

据说是为了防抄袭稍改了一下。

那就让本juruo来一篇高清无注释能AC方便直接复制粘贴的题解吧！

大概说说思路，具体的珂以根据代码看/自己思考（如果一步步跟着想的话并不难）。

首先，看起来是不是总觉得和排列组合有千丝万缕的联系？

一般排列组合常用什么方法？

两种：数学/DP。

数学方面这题输入实在太太太太多了，不考虑。

于是乎就只剩下了DP。

状态很好想，自然定义。

$dp_{i,a,b,c}$表示目前填第$i$行，第一列所有数目前和为$a$，二，三列依次为$b,c$的总方案数。

转移方程也很好想，无非就是枚举这一行三列依次放什么数。

接着开始优化，已经瞬间想出三个优化点的dalao可以跳过。

首先，状态定义。

我们已经知道了每一行三个数的和，因此前多少行总和我们不都是已知了？

所以如果已知$a,b$那$c$不就被唯一确定了？

然后状态珂以压到二维。

类似转移也珂以。

进一步优化：

你会发现每一个转移只与前一行有关。

所以还可以滚动数组~

完整代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e17;
int n,c[109],r[309];
int f[2][129][129];
signed main(){
	scanf("%lld%lld%lld%lld",&n,c+1,c+2,c+3);
	for(int i=1;i<=n;++i)scanf("%lld",r+i);
	//读入
	if(accumulate(r+1,r+n+1,-c[1]-c[2]-c[3]))return puts("0"),0;
	//特判给定条件矛盾
	f[0][0][0]=1;//前0行两列填0（那么第三列也是0）有一种
	for(int i=1;i<=n;++i)
	for(int j=0;j<=c[1];++j)
	for(int k=0;k<=c[2];++k){
		f[i&1][j][k]=0;//注意清零！！！
		for(int l=0;l<=j&&l<=r[i];++l)
		for(int m=0;m<=k&&l+m<=r[i];++m)
		f[i&1][j][k]=(f[i&1][j][k]+f[i&1^1][j-l][k-m])%mod;//枚举这一行放了什么
	}
	printf("%lld\n",f[n&1][c[1]][c[2]]);//输出
	return 0;
}