题目大意
给定 $n \le 500$ 个值的集合（值分别为 $a_i \le 500$）和一个值 $k \le 500$。 保证某个子集的和为 $k$。问对于子集和为 $k$ 的所有子集，有多少种不同的子集和，并输出这些可能得子集和。
简要题解
最初的想法是枚举这些可能的子集和值 $x$。但我们发现，用了一些点组成 $x$ 之后我们不知道其余的点是否可以组成 $k$。
改变思路，我们把 $01$ 背包下标是和加一维，$dp[i][j][k]$ 表示考虑了 $i$ 个物品后，总和为 $j$ 且对于 $x$ 的部分的和为 $x$ 是否可行。
于是转移就是三种，对 $i$ 物品，考虑
- 不选
- 选入组成 $k$ 的部分，不选入组成 $x$ 的部分
- 选入组成 $k$ 的部分，选入组成 $x$ 的部分
那么当所有物品都考虑完后，显然只需要看能组成 $k$ 的那些都能组成哪些 $x$ 即可。
显然第一维还是可以考滚动优化掉的。
复杂度
$T$：$O(n * k ^ 2)$
$S$：$O(k ^ 2)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n, k; cin >> n >> k;
vector<int> c(n);
for (int& i : c) cin >> i;
vector<vector<int>> dp(k + 1, vector<int>(k + 1, 0));
dp[0][0] = 1;
for (int v : c) {
for (int i = k; i >= 0; i--) {
for (int j = k; j >= 0; j--) {
if (!dp[i][j]) continue;
if (i + v > k) continue;
dp[i + v][j] = 1;
dp[i + v][j + v] = 1;
}
}
}
vector<int> ans;
for (int i = 0; i <= k; i++) {
if (dp[k][i]) ans.push_back(i);
}
int m = ans.size();
cout << m << '\n';
for (int i = 0; i < m; i++) {
cout << ans[i] << (" \n"[i == m - 1]);
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: B. Searching Rectangles - Codeforces Round 371 (Div. 1)