点右侧公式看它对应的块,或直接点图上的块。拖动滑块改变 L。
for (int t = 1; t <= lg; t++) {
int half = 1 << (t - 1); // 这一层的块边长
int quarter = (t >= 2) ? (1 << (t - 2)) : 0; // 补块偏移;t = 1 时没有补块
for (int i = 1; i + (1 << t) - 1 <= n; i++) {
for (int j = 1; j <= i; j++) {
int best = f[pre][i][j];
best = max(best, f[pre][i + half][j]);
best = max(best, f[pre][i + half][j + half]);
if (t > 1) {
best = max(best, f[pre][i + half][j + quarter]);
best = max(best, f[pre][i + quarter][j]);
best = max(best, f[pre][i + quarter][j + quarter]);
}
f[cur][i][j] = best;
}
}
swap(pre, cur);
}
for (int i = 1; i + k - 1 <= n; i++) {
int bottom = i + k - 1;
for (int j = 1; j <= i; j++) {
int right = j + k - 1;
int best = f[pre][i][j];
best = max(best, f[pre][bottom - block + 1][j]);
best = max(best, f[pre][bottom - block + 1][right - block + 1]);
if (lg >= 1) {
int cha = (k - block) / 2;
best = max(best, f[pre][bottom - block + 1][j + cha]);
best = max(best, f[pre][i + cha][j]);
best = max(best, f[pre][i + cha][j + cha]);
}
answer += best;
}
}
把滑块拖到 L = 8(边长 16),只点「只看 3 个角块」。空出多少格?
28 格。三个角块各边长 8,下面的两个角块在底边上错开 16 - 8 = 8 格,中间留下一块边长 7 的倒三角:7 + 6 + … + 1 = 28。L 越大,这个空洞增长得越快,所以补块不能省。
块 4 的上顶点是 (i + L/2, j)。如果把偏移改成 L,会发生什么?
选第一个。偏移取 L 时块 4 的上顶点就是 (i, j)… 正好和块 1 一模一样,6 个块塌成 3 个,边长 8 的例子会空出 6 格没盖住。偏移必须取半边 L/2,让补块卡进中间那块倒三角。这也是 L 只能取 2 的幂的原因:取奇数时 L/2 不是整数,落不到格子上。
下面是构建一层里取 6 个块的那几行,空格处填什么?(用 half、quarter、i、j 组合,例如 i + half)
int best = f[pre][i][j];
best = max(best, f[pre][i + half][j]);
best = max(best, f[pre][i + half][j + ]);
if (t > 1) {
best = max(best, f[pre][][j + quarter]);
best = max(best, f[pre][i + quarter][]);
best = max(best, f[pre][i + quarter][j + quarter]);
}
三个空依次是 half、i + half、j。
对着图看坐标:块 6 是 (i + L, j + L/2),块 3 是 (i + L, j + L),块 4 是 (i + L/2, j)。所以第一空是 half,第二空是 i + half,第三空是 j。