自动搬运

查看原文

来自洛谷，原作者为

	ycy1124 ENTJ-A | 有事私。| 清关了，私信基本也不会回关（除非满足条件），但可以支持小号回关 | 出去玩去了。不在线。微信可能上。

搬运于2025-08-24 23:02:57，当前版本为作者最后更新于2024-09-26 15:41:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

有 $a_1,a_2,a_3,a_4,a_5,a_6$ 块大小分别为 $1,2,3,4,5,6$ 的砖，问能否将其分成两部分并且大小之和相等。

思路

设总大小为 $sum$，那么只要能取出 $sum \div 2$ 大小的就一定可以，假如 $sum$ 不是偶数就可以直接输出 Can't 了。

对于 $sum$ 是偶数的，先将 $a_1,a_2,a_3,a_4,a_5,a_6$ 二进制拆分（拆分后一定可以反过来凑出 $1 \sim a_i$ 之间所有的整数，证明很简单，这里就不证了），然后直接 $01$ 背包就可以了。这里的 $dp_i$ 表示的是取出大小之和为 $i$ 的方案是否存在，最初时 $dp_0=1$。转移方程也很好想 $dp_i$ 明显只能由 $dp_{i-w_j}$ 得到（$1 \le j \le tot$ 且 $w_j \le i$），$w_j$ 表示的是第 $j$ 个物品的价值，$tot$ 表示的是物品总数。

代码

#include<bits/stdc++.h>
using namespace std;
int a[7];
int w[20001];
bool dp[210001];
int main(){
	int tot;
	while(scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6])){
		if((a[1]+a[3]+a[5])%2!=0){//不是偶数就直接输出Can't
			printf("Can't\n");
			continue;
		}
		memset(dp,0,sizeof(dp));//多测清空
		tot=0;
		if(a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0&&a[5]==0&&a[6]==0){
			return 0;
		}
		int js=(a[1]+a[2]*2+a[3]*3+a[4]*4+a[5]*5+a[6]*6)/2;//计算sum/2
		for(int i=1;i<=6;i++){
			int base=1;
			while(base<=a[i]){//二进制拆分
				a[i]-=base;
				w[++tot]=base*i;//体积和价值也等比例放大
				base*=2;
			}
			if(a[i]!=0){//这里别忘记把多余的加进去
				w[++tot]=a[i]*i;
			}
		}
		dp[0]=1;
		for(int i=1;i<=tot;i++){//完全背包
			for(int j=js;j>=w[i];j--){//遍历顺序别反了
				if(dp[j-w[i]]){
					dp[j]=1;
				}
			}
		}
		if(dp[js]){//假如sum/2可以
			printf("Can\n");
		}
		else{
			printf("Can't\n");
		}
	}
	return 0;
}

AC 记录。