1 条题解
-
0
[U] Grouping(dp_u)题解
题意简述
只兔子,分成若干组,同组内的每对 贡献 ,求总分最大值。。
思路
预处理:每组内部的收益
设 = 集合 的兔子全分在同一组时的总收益:
可以在 内递推:取 的最小元素 ,则 $g_S = g_{S \setminus \{i\}} + \sum_{j \in S\setminus\{i\}} a_{i,j}$。
集合划分 DP
设 = 把 划分成若干组能获得的最大收益。枚举"包含 最小元素的那一组" :
$$f_S = \max_{T \subseteq S,\; \min(S) \in T} \left( f_{S \setminus T} + g_T \right),\qquad f_\emptyset = 0.$$答案 。
固定"含最小元素的组"可以避免同一划分被多种顺序重复枚举。
为什么可以用"全负时取 0"来理解
若所有 ,最优解是每只兔子单独一组(组内无对,收益 )。所以答案下界是 (样例 2 就是 )。
复杂度
枚举所有子集再枚举子集的子集,总 ; 时 ,可过。空间 。
参考代码
#include <cstdio> #include <algorithm> using namespace std; long long a[16][16], g[1 << 16], f[1 << 16]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%lld", &a[i][j]); int full = 1 << n; for (int S = 1; S < full; S++) { int lo = __builtin_ctz(S), rest = S ^ (1 << lo); g[S] = g[rest]; for (int m = rest; m; m &= m - 1) g[S] += a[lo][__builtin_ctz(m)]; } for (int S = 1; S < full; S++) { int hi = S & -S; // 最小元素,必须属于被选出的组 long long best = -(1LL << 60); for (int m = S; m; m = (m - 1) & S) if (m & hi) best = max(best, f[S ^ m] + g[m]); f[S] = best; } printf("%lld\n", f[full - 1]); return 0; }易错点
- 必须固定最小元素再枚举组,否则同一划分被重复统计(虽然取 max 不影响结果,但会多算 倍时间)。
- 可为负, 的初值要用极小数,不能是 ——否则会把"单独成组"之外的坏方案当成更好。
- 结果可达 ,必须
long long(样例 3 是 )。 - 枚举子集的写法
m = (m-1) & S别写成m--。
数据说明
共 17 组:4 组官方样例;; 正/负; 正/负; 随机; 全正、全负、混合随机、全 (最大规模与最大和)。
- 1
信息
- ID
- 30
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者