测试点 1~3

给暴力搜索留的分。

测试点4~8

也是给暴力搜索留的分，只不过你需要转化一下问题。

我们考虑对于一个物品，他只有这三种情况：

• 被小 A 装在包里了，但落在路上了。
• 被小 A 装在包里了，并且带给小 B 了。
• 没有被小 A 装在包里。

所以这样搜索的时间复杂度就是 $O(3^n)$ 。

测试点9~12

或许有神秘 $O(n^4)$ 的 dp。

测试点13~16 17~20

我们设 $f_{i,j,k}$ 表示，考虑前 $i$ 个物品，被小 A 装在包里的物品总价值为 $j$ ，带给小 B 的物品总价值为 $k$ ，这样的方案是否存在。

考虑转移，对于一个物品 $w$：

• 被小 A 装在包里了，但落在路上了：$f_{i,j,k}\leftarrow f_{i-1,j-w,k}$。
• 被小 A 装在包里了，并且带给小 B 了。$f_{i,j,k}\leftarrow f_{i-1,j-w,k-w}$。
• 没有被小 A 装在包里。$f_{i,j,k}\leftarrow f_{i-1,j,k}$。

如果你不会滚动数组，就可以通过测试点13~16 ，通过滚动数组优化空间可以通过测试点 17~20

时间复杂度为 $O(n^3)$ 。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 510;
int n, m;
int f[maxn][maxn];
void slove() {
	cin >> n >> m;
	f[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		for (int j = m; j >= x; --j)
			for (int k = j; k >= 0; --k) {
				f[j][k] |= f[j - x][k];
				if (k - x >= 0)f[j][k] |= f[j - x][k - x];
			}
	}
	for (int i = 0; i <= m; ++i)
		if (f[m][i])printf("%d ", i);
}

int main() {

	int _ = 1;
	//cin >> _;
	while (_--) {
		slove();
	}
	return 0;
}