NOIP-模拟赛（五） 题解

候车供暖

简要题意

每组给定 $N$ 名乘客严格递增的到站时刻 $A_i$，每人停留到 $A_i+1$。暖炉初始关闭，有人在场时必须开启，至多启动 $K$ 次，求最少总开启时间。$1\le K\le N\le10^5$、$1\le A_i\le10^9$，最多 $10$ 组、同一输入中 $\sum N\le2\times10^5$，逐组输出一个整数。

一句话题解

从首位到站到末位离站的整段时间中，减去最大的 $K-1$ 段无人空档。

完整题解

从停留时间提取空档

第 $i$ 位乘客离开到第 $i+1$ 位乘客到达，中间无人区间长度是 $d_i=A_{i+1}-A_i-1$，不是两个到站时刻之差。所有 $d_i\ge0$，连续到访时也可能为 $0$。

如果始终不关暖炉，总开启时间为 $A_N-A_1+1$。在某段无人空档里关机、下一名乘客到来时重启，就恰好省去 $d_i$ 单位时间，并增加一次启动。起初至少启动一次，因此至多可以选择 $K-1$ 段空档。

最优性证明

在有人停留时不得关机；首位乘客之前和末位乘客之后开启暖炉没有收益。因此任意最优安排的额外开启部分都只可能出现在相邻乘客之间的无人空档内。在一段空档里若有关闭行为，将关闭时间扩展至整段不会影响乘客，只会使耗能不增，所以只需决定哪些整段空档关闭。

如果已选的某段空档比未选的一段短，交换二者不增加启动次数，却使总开启时间不增。不断交换即可得到最长的 $K-1$ 段空档。长度为 $0$ 的空档无需真的关闭；题目限制是“至多”，因此相同的最优值仍然可达。

故答案为

$$A_N-A_1+1-\sum_{i=1}^{K-1} d_{(i)},$$

其中 $d_{(i)}$ 按从大到小排列。时间复杂度 $O(N\log N)$，空间复杂度 $O(N)$。$N=1$ 时没有空档，答案为 $1$；$K=N$ 时答案为 $N$。答案不超过 $10^9$，本题使用 int 足够。

部分分路线

测试点 $1\sim4$：直接搜索相邻乘客之间是否关闭暖炉，记录已启动次数和当前耗能，枚举所有切分，复杂度 $O(2^N)$；非负费用可剪去不可能优于当前答案的分支。该路线对应 $20$ 分。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k, a[N], ans;
void dfs(int u, int cnt, int sum) {
	if (sum + n - u + 1 >= ans) return;
	if (u > n) {
		ans = sum;
		return;
	}
	if (cnt < k) dfs(u + 1, cnt + 1, sum + 1);
	dfs(u + 1, cnt, sum + a[u] - a[u - 1]);
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		ans = a[n] - a[1] + 1;
		dfs(2, 1, 1);
		cout << ans << "\n";
	}
	return 0;
}

测试点 $1\sim10$：令 $f_{i,j}$ 表示服务前 $i$ 人、启动 $j$ 次的最少总时间。第 $i$ 人到来时，要么从前一人处一直开启，增加 $A_i-A_{i-1}$；要么新启动一次，只增加 $1$。

$$f_{i,j}=\min(f_{i-1,j}+A_i-A_{i-1},\ f_{i-1,j-1}+1).$$

初值 $f_{1,1}=1$，其余为无穷大。从大到小枚举 $j$，可滚动为一维数组；总复杂度 $O(NK)$、空间 $O(K)$。恰好分成 $K$ 段的最优值等于至多 $K$ 段，因为拆开一段不会增加时间。此路线对应 $50$ 分。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 1e9;
int n, k, a[N], f[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		fill(f, f + k + 1, INF);
		f[1] = 1;
		for (int i = 2; i <= n; i ++)
			for (int j = min(i, k); j >= 1; j --)
				f[j] = min(f[j] + a[i] - a[i - 1], f[j - 1] + 1);
		cout << f[k] << "\n";
	}
	return 0;
}

容易失分的地方

• 空档必须减 $1$：到站时刻为 $1,2$ 时两人之间没有可省的空白时间。
• 最多省去 $K-1$ 段空档，不是 $K$ 段。例如 $K=1$ 时中途不能关闭。
• 要按空档长度选择，不能直接取最早出现的几段；到站时刻 $1,2,4$、$K=2$ 时，应省掉后面的空档，答案是 $3$。
• 每轮线性寻找剩余最大空档虽然思路正确，但总复杂度为 $O(NK)$，只能作为 $50$ 分路线，不能替代排序或堆。

满分参考程序

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k, a[N], d[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		for (int i = 1; i < n; i ++) d[i] = a[i + 1] - a[i] - 1;
		sort(d + 1, d + n, greater<int>());
		int ans = a[n] - a[1] + 1;
		for (int i = 1; i < k; i ++) ans -= d[i];
		cout << ans << "\n";
	}
	return 0;
}

---

墙面补色（mural）

简要题意

给定 $N$ 行三角形墙，第 $r$ 行有 $r$ 格，非底层格 $(r,c)$ 的两个下格是 $(r+1,c)$ 和 $(r+1,c+1)$。其中 $K$ 个互不相同的位置初始为黑，其余为白；只能补黑，要求最终每个非底层格为黑，当且仅当它的两个下格都为黑，求最少新增的黑格数。至多 $10$ 组，每组 $1\le N\le2\times10^9$、$1\le K\le\min(N(N+1)/2,1000)$，逐组输出一个整数。

一句话题解

每个初始黑格强制底边的一段整数区间变黑；合并相交或相邻的区间，每段长度 $L$ 贡献 $L(L+1)/2$ 个最终黑格，总和减去 $K$。

完整题解

先理解双向规则

把黑、白分别看作 $1,0$，每个非底层格的颜色恰好是两个下格的逻辑与。题目不只是要求黑格向下有支撑，还要求两个相邻黑格会向上生成黑格。

如果知道底行所有格子的颜色，倒数第二行便完全确定，继续向上即可确定整面墙。反过来，一个初始黑格又会强制其下方的格子为黑：$(r,c)$ 强制下一行的两格，再强制下下行的三格，最终要求底行的闭区间

$$[c,c+N-r]$$

全部为黑色。归纳可得，$(r,c)$ 最终为黑，当且仅当这段底行区间全部为黑。

为什么只涂区间并集就最优

设所有初始黑格对应的底边区间的并集为 $U$。

任何合法终态都必须把 $U$ 中的底格涂黑，否则至少有一个初始黑格得不到支撑。现在恰好把 $U$ 涂黑，其余底格保留白色，再按照逻辑与逐层向上确定颜色。每个初始黑格所对应的底边区间都已全部变黑，所以原来的黑格仍然为黑；每格的颜色又正是两个下格的逻辑与，因此这个终态合法。

增加底边黑格只可能使更多的上层格变黑，不可能减少黑格。任何合法终态的底边都包含 $U$，所以以上构造的黑格总数最少。

合并时不能漏掉相邻区间

底边是整数格子。例如区间 $[1,2]$ 和 $[3,4]$ 之间没有白格，它们构成一个长度为 $4$ 的连续黑段，必须合并。排序以后，只要下一个区间的左端点不超过当前右端点加 $1$，便应合并，并把右端点取两者的较大值。

一个长度为 $L$ 的连续黑段，上一行形成 $L-1$ 个黑格，再往上是 $L-2$ 个，直到 $1$ 个。因此它总共形成

$$1+2+\cdots+L=\frac{L(L+1)}2$$

个黑格。不同极大连续黑段之间有白格，它们不会共同生成横跨白格的黑格，贡献可以分别累加。最后减去最初的 $K$ 个黑格，才是需要新增的数量。

排序合并的时间复杂度为 $O(K\log K)$，空间复杂度为 $O(K)$。本题 $K\le1000$，正确的 $O(K^2)$ 区间整理也足够完成满分范围，不必执着于排序模板。

部分分与赛时路线

路线	做法与适用范围	累计分数
单黑格	$K=1$ 时计算其强制三角形的格数减一	5
两个黑格	$K\le2$ 时分相交、相邻、分离讨论两个底边区间	15
特殊性质加小墙模拟	再处理 $N=2$，以及 $N\le20$ 的反复规则传播	35
特殊性质加两趟传播	小 $K$ 用公式；其余向下传播后向上重建，$N\le3000$	55
特殊性质加底行扫描	小 $K$ 用公式；其余底边差分/端点事件扫描，$N\le10^6$	75
完整区间模型	不再遍历底边，只处理 $K$ 个区间	100

这几档是包含小 $K$ 分支的累计路线；仅写一个二维小数组而不处理大 $N$ 的 $K=1,2$，不能获得前 $15$ 分。

小墙可以反复检查每个父格与两个子格，发现规则要求补黑就执行，直到一整轮没有变化。过程只增加黑格，每步都是任何合法终态必须进行的补色，所以得到最小闭包。不能只扫一遍就认为所有反向影响已经处理。

二维两趟法更快：先从上到下，把每个黑格的两个子格置黑。这一趟完成全部向下强制；之后只保留得到的底边，按逻辑与从下往上重建。这恰好是前述最小合法终态，时间和空间都是 $O(N^2)$。参考程序按真实墙面规模申请空间，大范围超出内存限制属于这种算法本身的限制，不使用人为的范围判断输出错误答案。

底行扫描法先记录每个区间起点的 $+1$ 事件和右端点后一格的 $-1$ 事件，再逐个底格扫描。当前覆盖数大于零时，令连续黑段长度加一，并把这一长度加入答案；否则长度清零。一个长度 $L$ 的黑段会贡献 $1+\cdots+L$。可以用数组差分，也可以排序至多 $2K$ 个端点事件，后者空间为 $O(K)$，时间为 $O(N+K\log K)$。大 $N$ 的小 $K$ 仍须单独使用公式，不能逐格扫描到 $2\times10^9$。

部分分参考实现

小 $K$ 加逐格闭包：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1010;
PII a[N];
set<PII> s;
int n, k;
LL tri(LL x) {
	return x * (x + 1) / 2;
}
LL small_k() {
	LL l1 = a[1].second, r1 = l1 + n - a[1].first;
	if (k == 1) return tri(r1 - l1 + 1) - 1;
	LL l2 = a[2].second, r2 = l2 + n - a[2].first;
	if (l1 > l2) swap(l1, l2), swap(r1, r2);
	if (l2 <= r1 + 1) return tri(max(r1, r2) - l1 + 1) - 2;
	return tri(r1 - l1 + 1) + tri(r2 - l2 + 1) - 2;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		s.clear();
		for (int i = 1; i <= k; i ++) cin >> a[i].first >> a[i].second;
		if (k <= 2) {
			cout << small_k() << "\n";
			continue;
		}
		for (int i = 1; i <= k; i ++) s.insert(a[i]);
		bool change = true;
		while (change) {
			change = false;
			for (int r = 1; r < n; r ++)
				for (int c = 1; c <= r; c ++) {
					if (s.count({r, c})) {
						change |= s.insert({r + 1, c}).second;
						change |= s.insert({r + 1, c + 1}).second;
					}
					if (s.count({r + 1, c}) && s.count({r + 1, c + 1}))
						change |= s.insert({r, c}).second;
				}
		}
		cout << (LL)s.size() - k << "\n";
	}
	return 0;
}

小 $K$ 加二维两趟传播：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1010;
PII b[N];
unsigned char *a;
int n, k;
LL pos(int r, int c) {
	return (LL)r * (r - 1) / 2 + c - 1;
}
LL tri(LL x) {
	return x * (x + 1) / 2;
}
LL small_k() {
	LL l1 = b[1].second, r1 = l1 + n - b[1].first;
	if (k == 1) return tri(r1 - l1 + 1) - 1;
	LL l2 = b[2].second, r2 = l2 + n - b[2].first;
	if (l1 > l2) swap(l1, l2), swap(r1, r2);
	if (l2 <= r1 + 1) return tri(max(r1, r2) - l1 + 1) - 2;
	return tri(r1 - l1 + 1) + tri(r2 - l2 + 1) - 2;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		for (int i = 1; i <= k; i ++) cin >> b[i].first >> b[i].second;
		if (k <= 2) {
			cout << small_k() << "\n";
			continue;
		}
		// 按真实规模保存整面墙；大规模会自然超过内存限制。
		a = new unsigned char[tri(n)]();
		for (int i = 1; i <= k; i ++) a[pos(b[i].first, b[i].second)] = 1;
		for (int r = 1; r < n; r ++)
			for (int c = 1; c <= r; c ++)
				if (a[pos(r, c)]) a[pos(r + 1, c)] = a[pos(r + 1, c + 1)] = 1;
		for (int r = n - 1; r >= 1; r --)
			for (int c = 1; c <= r; c ++)
				a[pos(r, c)] = a[pos(r + 1, c)] && a[pos(r + 1, c + 1)];
		LL ans = -k;
		for (LL i = 0; i < tri(n); i ++) ans += a[i];
		cout << ans << "\n";
		delete[] a;
	}
	return 0;
}

小 $K$ 加底行扫描：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2010;
PII a[N];
int n, k;
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		for (int i = 1; i <= k; i ++) {
			int r, c;
			cin >> r >> c;
			a[i * 2 - 1] = {c, 1};
			a[i * 2] = {c + (n - r) + 1, -1};
		}
		sort(a + 1, a + 2 * k + 1);
		if (k <= 2) {
			LL ans = -k, len = 0;
			int cnt = 0, last = 1;
			for (int i = 1; i <= 2 * k; ) {
				if (cnt) len += a[i].first - last;
				else ans += len * (len + 1) / 2, len = 0;
				last = a[i].first;
				while (i <= 2 * k && a[i].first == last) cnt += a[i ++].second;
			}
			ans += len * (len + 1) / 2;
			cout << ans << "\n";
			continue;
		}
		LL ans = -k, len = 0;
		int j = 1, cnt = 0;
		for (int i = 1; i <= n; i ++) {
			while (j <= 2 * k && a[j].first == i) cnt += a[j ++].second;
			if (cnt) len ++;
			else len = 0;
			ans += len;
		}
		cout << ans << "\n";
	}
	return 0;
}

容易走错的方向

1. 只向下补黑。 $N=3$，初始黑格为 $(3,1),(3,2)$ 时，还必须把 $(2,1)$ 涂黑，答案为 $1$。
2. 只合并相交、不合并相邻。 上面的两格分别投影为 $[1,1]$ 和 $[2,2]$，合起来是连续的两格，不能分别计算。
3. 把所有区间的最左、最右端点之间全涂黑。 $N=3$，初始为 $(3,1),(3,3)$ 时，中间有白格，无须补色，答案为 $0$；强行连成一个三角形会多涂。
4. 各三角形分别求和，或只减两两交集。 重叠会重复计数，三重覆盖又需要恢复；此外原来不相交、只相邻的底边会产生新的上层格，单纯计算原三角形面积并集也不是最终闭包。
5. 合并时用新区间右端点直接覆盖旧右端点。 新区间可能被旧区间包含，应始终取最大值。

整数范围与满分代码

最多可能有 $N(N+1)/2=2000000001000000000$ 个黑格，需要 long long。乘法的两个操作数必须先处于 64 位类型，不能先以 int 相乘再赋给长整数。输入格子保证互不相同，所以最后直接减 $K$；每组重新初始化当前区间和答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;
const int N = 1010;
PII a[N];
int n, k;
LL calc(LL len) {
	return len * (len + 1) / 2;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		for (int i = 1; i <= k; i ++) {
			int r, c;
			cin >> r >> c;
			a[i] = {c, (LL)c + n - r};
		}
		sort(a + 1, a + k + 1);
		LL l = a[1].first, r = a[1].second, ans = 0;
		for (int i = 2; i <= k; i ++) {
			if (a[i].first <= r + 1) r = max(r, a[i].second);
			else {
				ans += calc(r - l + 1);
				l = a[i].first, r = a[i].second;
			}
		}
		ans += calc(r - l + 1);
		cout << ans - k << "\n";
	}
	return 0;
}

---

饭团合并（merge）

简要题意

给出从左到右 $N$ 个正整数大小的饭团：当前相邻的两个饭团大小相等时可以合并，当前相邻的三个饭团两端大小相等时也可以一起合并，中间大小不限。合并后大小为总和，求任意操作序列中能够得到的最大单个饭团，不要求合并整行。每组 $1\le N\le1200$、$1\le a_i\le10^6$，至多 $10$ 组，同一输入文件 $\sum N^3\le3456000000$；每组输出一个整数。

一句话题解

区间 DP 按最后一次合并拆成两块或三块，再利用正数前缀和的单调性，用双指针寻找等重的外侧两块。

完整题解

从真实操作到区间

每个新饭团都由原序列中连续的一段合并而成。最初每个饭团对应一个单点区间，之后只有相邻饭团可以合并，因此这个性质始终成立。

设 $f[l][r]$ 表示原序列的区间 $[l,r]$ 能否合成一个饭团，$s_i=\sum_{j=1}^{i}a_j$。单点显然可以，故 $f[i][i]=\mathrm{true}$。

如果一个长度大于 $1$ 的区间能够合并，考虑它的最后一次操作：参与的只能是两个或三个已经合好的连续区间。因此存在 $l\le i<j\le r$，满足：

• $f[l][i]$ 和 $f[j][r]$ 都为真；
• 两侧大小相等，即 $s_i-s_{l-1}=s_r-s_{j-1}$；
• 中段为空，即 $i+1=j$，或者 $f[i+1][j-1]$ 为真。

反过来，满足这些条件时，先把各个非空区间合好，再执行一次合法的二元或三元合并，便能得到整个区间。这说明条件既必要又充分。

按区间长度从小到大计算，转移依赖的区间均更短。答案是所有可合区间的区间和最大值，而不是只看 $f[1][N]$。允许零次操作，所以单点也参与答案。

55 分：枚举两个分界

对每个 $[l,r]$，枚举两侧区间的端点 $i,j$，直接判断上述条件。共有 $O(N^2)$ 个区间，每个区间枚举 $O(N^2)$ 个分界，时间 $O(N^4)$，空间 $O(N^2)$。

可以跳过不可合的外侧区间，也可以在找到一个方案后立即停止，但最坏情况下仍会枚举大量分界。$N\le50$ 的范围可以直接完成；不应仅因随机大值几乎没有可合区间，就认为这种方法在满分范围也足够快。

100 分：双指针只访问可能等重的分界

固定区间 $[l,r]$，从 $i=l,j=r$ 开始，令

$$x=s_i-s_{l-1},\qquad y=s_r-s_{j-1}.$$

在 $i<j$ 时：

• 若 $x<y$，增加 $i$，扩大左段；
• 若 $x>y$，减小 $j$，扩大右段；
• 若 $x=y$，检查两侧和中段的可合性。成功即令 $f[l][r]$ 为真；失败则同时增加 $i$、减小 $j$，继续寻找下一对等重分界。

为什么不会漏解？ 所有 $a_i$ 都是正数，因此两侧区间扩张时，大小严格增大。若 $x<y$，保持左段不变而继续扩大右段只会使差距更大，当前 $i$ 不可能再匹配任何后续右段，必须推进左侧；另一种大小关系同理。若两侧已经相等但可合性不满足，保持任意一侧、只扩大另一侧也不可能继续相等，所以可以同时推进。每次都只舍弃不可能的分界，不会漏掉合法方案。

相等只表示大小匹配，不表示两个外段或中段一定能够各自合成一个饭团，三处可合性检查不能省略。第一处等重分界检查失败以后，也不能立即宣布整个区间不可合。

每个区间中 $i$ 至多向右移动 $N$ 次，$j$ 至多向左移动 $N$ 次，因此每个区间 $O(N)$，总时间 $O(N^3)$、空间 $O(N^2)$。

部分分与赛时路线

路线	适用公开范围	做法	得分
四个饭团	$N=4$	只处理长度不超过 $4$ 的区间，枚举两个分界	5
真实操作搜索	$N\le10$	枚举当前序列上的二元、三元合并，记忆化去重	20
普通区间 DP	$N\le50$	枚举每个区间的两处分界	55
双指针区间 DP	全部范围	利用正数性，只检查两侧等重的分界	100

搜索时，每个状态是一整行当前饭团大小。遍历所有合法操作并递归，保存每个状态可以取得的最大大小；如果已经取得本行总和就可以提前结束。该方法直接对应题意，不依赖区间 DP 的转移。状态数最坏是指数级：每个当前饭团对应一个原序列连续块，连续分块最多 $2^{N-1}$ 种；每个状态枚举、复制操作至多 $O(N^2)$，粗略上界为 $O(N^2 2^N)$。记忆化不能使它成为多项式算法。

赛时可以先写正确的操作搜索确认二元、三元规则，再从“新饭团总是一段区间”转向区间 DP。四次方版本容易得到完整转移；最后用正数性缩减分界枚举，而不是凭直觉决定合并顺序。

部分分参考实现

只处理最多四个原始饭团的区间，完整覆盖第一个测试点：

#include<bits/stdc++.h>
using namespace std;
const int N = 1605;
int n, a[N], sum[N];
bool f[N][N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		int ans = 0;
		for (int i = 1; i <= n; i ++) {
			cin >> a[i];
			sum[i] = sum[i - 1] + a[i];
			memset(f[i], 0, (n + 1) * sizeof(bool));
			f[i][i] = true;
			ans = max(ans, a[i]);
		}
		// 只寻找最多四个原始饭团能合出的结果。
		for (int len = 2; len <= min(n, 4); len ++)
			for (int l = 1; l + len - 1 <= n; l ++) {
				int r = l + len - 1;
				for (int i = l; i < r; i ++)
					for (int j = i + 1; j <= r; j ++)
						if (f[l][i] && f[j][r] && (i + 1 == j || f[i + 1][j - 1]) && sum[i] - sum[l - 1] == sum[r] - sum[j - 1]) f[l][r] = true;
				if (f[l][r]) ans = max(ans, sum[r] - sum[l - 1]);
			}
		cout << ans << "\n";
	}
	return 0;
}

枚举当前饭团序列上的真实操作，使用记忆化，覆盖前四个测试点：

#include<bits/stdc++.h>
using namespace std;
const int N = 1605;
int n, a[N][N];
unordered_map<string, int> mem;
int dfs(int u, int m) {
	string key;
	key.reserve(m * 4);
	int ans = 0, sum = 0;
	for (int i = 1; i <= m; i ++) {
		ans = max(ans, a[u][i]);
		sum += a[u][i];
		for (int j = 0; j < 4; j ++) key += char((a[u][i] >> (j * 8)) & 255);
	}
	auto it = mem.find(key);
	if (it != mem.end()) return it->second;
	for (int k = 2; k <= 3; k ++)
		for (int l = 1; l + k - 1 <= m; l ++) {
			if (a[u][l] != a[u][l + k - 1]) continue;
			int cnt = 0, cur = 0;
			for (int i = 1; i < l; i ++) a[u + 1][++ cnt] = a[u][i];
			for (int i = l; i < l + k; i ++) cur += a[u][i];
			a[u + 1][++ cnt] = cur;
			for (int i = l + k; i <= m; i ++) a[u + 1][++ cnt] = a[u][i];
			ans = max(ans, dfs(u + 1, cnt));
			if (ans == sum) return mem[key] = ans;
		}
	return mem[key] = ans;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> a[0][i];
		mem.clear();
		cout << dfs(0, n) << "\n";
	}
	return 0;
}

带可合性剪枝和成功早停的四次区间 DP，覆盖前十一个测试点：

#include<bits/stdc++.h>
using namespace std;
const int N = 1605;
int n, a[N], sum[N];
bool f[N][N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) {
			cin >> a[i];
			sum[i] = sum[i - 1] + a[i];
			memset(f[i], 0, (n + 1) * sizeof(bool));
			f[i][i] = true;
		}
		int ans = 0;
		for (int len = 1; len <= n; len ++)
			for (int l = 1; l + len - 1 <= n; l ++) {
				int r = l + len - 1;
				for (int i = l; i < r && !f[l][r]; i ++) {
					if (!f[l][i]) continue;
					for (int j = r; j > i; j --) {
						if (!f[j][r]) continue;
						int x = sum[i] - sum[l - 1], y = sum[r] - sum[j - 1];
						#ifdef PRUNE
						if (y > x) break;
						#endif
						if (x == y && (i + 1 == j || f[i + 1][j - 1])) {
							f[l][r] = true;
							break;
						}
					}
				}
				if (f[l][r]) ans = max(ans, sum[r] - sum[l - 1]);
			}
		cout << ans << "\n";
	}
	return 0;
}

容易走错的方向

1. 只考虑两个相等饭团。 序列 $1,1,1$ 可以一次三元合并得到 $3$；只合相邻两个最多得到 $2$。
2. 局部选择最大的合并。 序列 $1,1,1,1$ 中，若先合并三个得到 $3,1$，就不能得到正确的 $4$。改变扫描方向、试几种优先级取最好，也没有穷尽所有合并顺序。
3. 不检查外段能否合并。 序列 $1,2,3$ 左边两项总和与右边一样，但 $1,2$ 不能先合成一个饭团，答案为 $3$，不是 $6$。
4. 不检查中段能否合并。 序列 $1,1,2,1$ 的两端相等，但中间 $1,2$ 不可合，不能直接取总和 $5$；正确答案为 $4$。
5. 第一处等重分界失败就退出。 序列 $1,1,2,1,2,1$ 可以全部合成 $8$；第一处两端均为 $1$ 的分界不满足中段可合，仍需继续找。
6. 只求覆盖整个序列或从开头出发的区间。 原样例最优饭团不包含最左端的 $47$。答案应枚举所有可合区间。

实现边界与满分代码

数据保证正整数，这是双指针正确性的关键。每组重新清空 $f$，单点初始化为真；两个外段相邻时，中段为空，不能访问一个未定义的空区间状态来替代判断。总大小不超过 $1200\times10^6=1.2\times10^9$，前缀和和答案使用 32 位有符号整数是安全的。

#include<bits/stdc++.h>
using namespace std;
const int N = 1605;
int n, a[N], sum[N];
bool f[N][N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) {
			cin >> a[i];
			sum[i] = sum[i - 1] + a[i];
			memset(f[i], 0, (n + 1) * sizeof(bool));
			f[i][i] = true;
		}
		int ans = 0;
		for (int len = 1; len <= n; len ++)
			for (int l = 1; l + len - 1 <= n; l ++) {
				int r = l + len - 1, i = l, j = r;
				while (!f[l][r] && i < j) {
					int x = sum[i] - sum[l - 1], y = sum[r] - sum[j - 1];
					if (x < y) i ++;
					else if (x > y) j --;
					else {
						if (f[l][i] && f[j][r] && (i + 1 == j || f[i + 1][j - 1])) f[l][r] = true;
						i ++, j --;
					}
				}
				if (f[l][r]) ans = max(ans, sum[r] - sum[l - 1]);
			}
		cout << ans << "\n";
	}
	return 0;
}

---

雪球增重（drift）

简要题意

数轴上有 $N$ 个初始重量为 $0$ 的雪球，给出它们严格递增的整数初始位置 $X_i$，以及 $Q$ 天的整数位移 $W_j$。每天所有雪球同时、同速平移，只有第一个经过某段雪地的雪球能取得这段雪，已经取走的雪不会再生。每个文件至多 $10$ 组，每组 $N,Q\le2\times10^5$，$|X_i|,|W_j|\le10^{12}$，同文件的 $\sum N,\sum Q$ 分别不超过 $4\times10^5$；按原编号逐行输出各雪球最终取得的雪的长度。

一句话题解

维护累计位移的左右历史极值，对每个相邻间隙二分首次扫满的时刻，再按当天扩展方向确定两侧雪球各自取得的长度。

完整题解

一、所有雪球共享一条位移轨迹

令 $p_0=0$，$p_t=W_1+\cdots+W_t$。第 $t$ 天结束时，第 $i$ 个雪球位于 $X_i+p_t$。

只看 $p_Q$ 不够，因为走过又折返的雪也已经被收走；把 $|W_j|$ 相加也不对，因为重复经过不会再次增重。应记录历史上向左、向右到达过的最远距离：

$$L_t=-\min_{0\le j\le t}p_j,\qquad R_t=\max_{0\le j\le t}p_j.$$

它们均非负、单调不减，且必须把初始位置对应的 $p_0=0$ 算进去。

二、35 分：按天、按雪球计算新收走的区间

设某天开始前的覆盖宽度为 $D=L+R$。如果当天向右创造了新极值，新扩展长度为 $\Delta$，则第 $i<N$ 个雪球新增重量为

$$\min\bigl(\Delta,\max(0,X_{i+1}-X_i-D)\bigr),$$

最右侧雪球则新增 $\Delta$。原因是初始间隙中此前尚未扫过的长度恰为 $\max(0,X_{i+1}-X_i-D)$，右移只能由左端雪球取得这些剩余的雪。

向左创造新极值时对称处理，第 $i>1$ 个雪球使用左侧间隙，最左侧雪球新增 $\Delta$。未创造新极值的移动只经过旧雪地，没有贡献。

每个创新极值的日子扫描所有雪球，时间 $O(NQ)$，空间 $O(N)$；可获得测试点 $1\sim7$ 的 35 分。这里按整段长度计算，不能每移动一个单位就循环一次，因为小档的 $|W_j|$ 也可能达到 $10^{12}$。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, q;
LL x[N], ans[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> q;
		for (int i = 1; i <= n; i ++) cin >> x[i], ans[i] = 0;
		LL now = 0, l = 0, r = 0;
		for (int j = 1; j <= q; j ++) {
			LL w;
			cin >> w;
			now += w;
			LL d = l + r;
			if (now > r) {
				LL add = now - r;
				for (int i = 1; i < n; i ++)
					ans[i] += min(add, max(0LL, x[i + 1] - x[i] - d));
				ans[n] += add;
				r = now;
			} else if (-now > l) {
				LL add = -now - l;
				for (int i = 2; i <= n; i ++)
					ans[i] += min(add, max(0LL, x[i] - x[i - 1] - d));
				ans[1] += add;
				l = -now;
			}
		}
		for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
	}
	return 0;
}

三、把逐天重复处理改为逐间隙处理一次

把初始数轴分为两个外侧区间，以及 $N-1$ 个相邻雪球间的间隙。考虑长度为 $d=X_{i+1}-X_i$ 的间隙。

间隙中的雪只可能先被第 $i$ 或第 $i+1$ 个雪球收走。更靠左的雪球若想先取得该间隙中的某点，第 $i$ 个雪球必须先经过它；右侧同理。雪球始终同速且保持顺序，故不存在第三个雪球抢先取得间隙内雪的情况。

在间隙还未扫满时，左雪球从左端取得 $R_t$，右雪球从右端取得 $L_t$，剩余长度为 $d-L_t-R_t$。我们只需知道它何时第一次扫满，以及最后一段雪由谁取得。

四、二分首次扫满的时刻

如果 $L_Q+R_Q<d$，到最后仍有雪没有被取得，直接向左雪球加 $R_Q$、向右雪球加 $L_Q$。

否则，由于 $L_t+R_t$ 单调不减，可以二分最小的 $t$，使得

$$L_t+R_t\ge d.$$

在第 $t-1$ 天结束时，间隙尚未扫满。当天所有雪球只向一个方向移动，所以不可能同时新增左右两个极值。

• 若 $R_t>R_{t-1}$，说明当天向右扩展。右雪球此前取得了 $L_{t-1}$，余下的雪全由左雪球取得，贡献分别为 $d-L_{t-1}$ 与 $L_{t-1}$。
• 否则，当天向左扩展。左雪球此前取得了 $R_{t-1}$，贡献分别为 $R_{t-1}$ 与 $d-R_{t-1}$。

间隙扫满后再也没有新雪，不用继续模拟。最后给第 $1$ 个雪球加上最左外侧的 $L_Q$，给第 $N$ 个雪球加上最右外侧的 $R_Q$。当 $N=1$ 时，两项都应加给同一个雪球。

也可以二分首次严格大于 $d$ 的时刻，只要同时将“最终未严格超过”的分支与分配公式正确配套。这是另一种正确的边界约定，不能单凭比较符号与标程不同就判错。

五、正确性证明

首先，所有雪球始终相差固定的初始间距。因此，某初始间隙中的雪若从左侧被首次经过，一定由紧邻左端的雪球取得；从右侧同理。

其次，单个雪球走过的路线连续，历史位移覆盖区间为 $[-L_t,R_t]$。在相邻雪球的覆盖尚不相交时，间隙两端取得的雪长分别为 $R_t,L_t$，互不重复。

最后，二分得到的 $t$ 是覆盖第一次相交或接触的时刻。之前两侧取得的雪已经固定；当天只有一个方向扩展，剩余雪必全归向间隙内部继续扩展的那一端。算法给出的两项贡献相加恰为 $d$，且保留另一端此前的贡献，故分配正确。未扫满的间隙和两个外侧区间也分别按实际历史覆盖长度计数。

各区间互不重叠且覆盖整条初始雪地，累加它们的正确贡献，即得到每个雪球的最终重量。

六、复杂度与实现边界

预处理极值序列需要 $O(Q)$ 时间，每个间隙二分 $O(\log Q)$，总时间 $O(Q+N\log Q)$，空间 $O(N+Q)$。

累计位移的绝对值可能达到 $2\times10^{17}$，不能用 int。位置、风力、累计位移、历史极值和答案统一用 long long。每组清空当前使用的答案段，并重设 $L_0=R_0=0$。

将间隙按长度排序，再按极值变化顺序处理，也能达到 $O(Q+N\log N)$，属于合法满分算法。

七、容易出错的方向

1. 把路程当作增重。 只有一个雪球、位移依次为 $3,-3,3$ 时，最终重量是 $3$，不是 $9$。
2. 只看最终位移。 初始位置为 $0,10$，位移为 $3,-1$ 时，两球各取得 $3$，不是 $2$。
3. 只看最终极值，再随意分配重叠部分。 初始位置为 $0,3$，位移为 $-2,4$ 时，间隙先被右球取得 $2$，再被左球取得剩余的 $1$；两球最终重量为 $3,4$。历史顺序不能丢。
4. 每个雪球依次走完整天。 初始位置为 $0,1$，当天右移 $2$ 时，正确重量为 $1,2$；按编号让左球先走完整段会抢走本应由右球先经过的雪。
5. 慢解只靠提前停止。 若每天只使覆盖宽度增加很少，且间隙各不相同，每个间隙仍可能扫描大量天。只处理创新极值日或缓存相同间隙也不能保证满分复杂度。

八、满分参考实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, q;
LL x[N], l[N], r[N], ans[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> q;
		for (int i = 1; i <= n; i ++) cin >> x[i], ans[i] = 0;
		LL now = 0;
		l[0] = r[0] = 0;
		for (int i = 1; i <= q; i ++) {
			LL w;
			cin >> w;
			now += w;
			l[i] = max(l[i - 1], -now);
			r[i] = max(r[i - 1], now);
		}
		ans[1] += l[q], ans[n] += r[q];
		for (int i = 1; i < n; i ++) {
			LL d = x[i + 1] - x[i];
			if (l[q] + r[q] < d) {
				ans[i] += r[q], ans[i + 1] += l[q];
				continue;
			}
			int a = 1, b = q;
			while (a < b) {
				int mid = a + b >> 1;
				if (l[mid] + r[mid] >= d) b = mid;
				else a = mid + 1;
			}
			if (r[a] > r[a - 1]) {
				ans[i] += d - l[a - 1];
				ans[i + 1] += l[a - 1];
			} else {
				ans[i] += r[a - 1];
				ans[i + 1] += d - r[a - 1];
			}
		}
		for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
	}
	return 0;
}