题解

思路分析

这是一道 状态压缩DP + 二分答案 的优化问题。

问题建模

• 将 $n \times m$ 的网格用 $r$ 条横线和 $s$ 条竖线分成 $(r+1) \times (s+1)$ 个矩形
• 每个矩形的计算时间 = 矩形内所有单元格时间之和
• 目标：最小化所有矩形中的最大计算时间

核心思路

1. 二分答案

二分最大计算时间 $mid$，判断是否存在一种分割方案使得所有矩形时间 $\leq mid$。

2. 状态压缩DP验证可行性

对于固定的 $mid$，判断能否分割：

横向划分（行）：

• 枚举所有可能的竖线放置方案（状态压缩）
• 对于每种竖线方案，检查横线的划分是否可行

DP状态定义：

• $dp[i][mask]$ 表示前 $i$ 行，使用竖线分割方案 $mask$ 时，是否可行

转移：

• 枚举当前这一段行的结束位置
• 检查这一段内，每个竖条（列组）的和是否 $\leq mid$
• 如果可行，转移到下一段

3. 前缀和优化

预处理行/列的前缀和，快速计算矩形区域的和。

算法步骤

1. 预处理前缀和：

   • $sum[i][j] = \sum_{k=1}^{j} a[i][k]$（第 $i$ 行前 $j$ 列的和）

2. 枚举竖线方案（$2^{m-1}$ 种）：

   • 确定 $s+1$ 个竖条的列范围 $[l_k, r_k]$
   • 跳过超过 $s$ 条竖线的方案

3. 二分答案 + DP验证：

   • 二分 $mid$（最大计算时间）
   • 对于每个竖线方案，DP判断横线划分是否可行
   • 如果存在可行方案，缩小上界；否则扩大下界

4. 输出答案

复杂度分析

• 枚举竖线方案：$O(2^m)$
• 二分：$O(\log(\text{sum}))$
• DP验证：$O(n^2)$（每种方案）
• 总时间复杂度：$O(2^m \cdot n^2 \cdot \log(\text{sum}))$
• 空间复杂度：$O(n \cdot m)$

由于 $n, m \leq 18$，$2^{18} \approx 2.6 \times 10^5$ 可以接受。

# include <bits/stdc++.h>
using namespace std;
const int N = 20 + 5, M = 20 + 5;
int n, m, rmax, smax;
int a [N] [M], sum [N] [M];
int l [M], r [M];
int all = 0;
int sz [M];
int check (int w, int tot) {
	int cnt = 0;
	for (int i = 1; i <= tot; ++ i) {
		sz [i] = 0;
	}
	for (int i = 1; i <= n && cnt <= rmax; ++ i) {
		for (int j = 1; j <= tot; ++ j) {
			sz [j] += sum [i] [r [j]] - sum [i] [l [j] - 1];
		}
		for (int j = 1; j <= tot; ++ j) {
			if (sz [j] > w) {
				for (int k = 1; k <= tot; ++ k) {
					sz [k] = sum [i] [r [k]] - sum [i] [l [k] - 1];
				}
				++ cnt;
				break;
			}
		}
	}
	return cnt <= rmax;
}
int Search (int tot) {
	int L = 0, R = all, ans = all;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= tot; ++ j) {
			L = max (L, sum [i] [r [j]] - sum [i] [l [j] - 1]);
		}
	}
	while (L <= R) {
		int mid = (L + R) >> 1;
		if (check (mid, tot)) {
			ans = mid;
			R = mid - 1;
		}
		else { 
			L = mid + 1;
		}
	}
	return ans;
}
int main () {
	scanf ("%d %d %d %d", & n, & m, & rmax, & smax);
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			scanf ("%d", & a [i] [j]);
			all += a [i] [j];
		}
	}
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			sum [i] [j] = sum [i] [j - 1] + a [i] [j];
		}
	}
	int ans = all;
	for (int i = 0; i < (1 << (m - 1)); ++ i) {
		int tot = 1;
		l [1] = 1;
		for (int j = 1; j <= m - 1; ++ j) {
			if ((i >> (j - 1)) & 1) {
				r [tot] = j;
				++ tot;
				l [tot] = j + 1;
			}
		}
		r [tot] = m;
		if (tot > smax + 1) {
			continue;
		}
		ans = min (ans, Search (tot));
	}
	printf ("%d", ans);
	return 0;
}

题解

我们需要选择 $r$ 条水平切线与 $s$ 条竖直切线，使得每个小矩形的权值和不超过某个上限 $W$，并让 $W$ 尽量小。由于 $n,m\le 18$，横向切的位置数量不多，可以先枚举竖向切点，再对每种竖向切法做二分/检查：

1. 枚举竖划分：用一个位掩码表示在第 $j$ 条子午线之后是否切一刀。这样可以把列分成若干连续段（不超过 $s+1$ 段），限制超过就跳过。
2. 前缀和预处理：对每行求前缀和 sum[i][j]，方便在 $O(1)$ 时间求出某行某个列段的权值。
3. 给定竖划分后二分答案：下界设为单个行段所需的最大值，上界为总和 all。检查函数 check(mid) 按行从上到下累积每个竖直段的和，如果某段超过 mid 就认为必须在上一行切一条水平线，并清空累积值。统计所需的水平切线条数，若不超过 $r$ 即可。

对子集枚举与二分取最小值。由于竖向有 $m-1$ 个潜在切点，枚举的次数为 $O(2^{m-1})$，每次检查在 $O(n \cdot \text{段数})$ 时间内完成，总体复杂度在数据范围内轻松通过。

# include <bits/stdc++.h>
using namespace std;
const int N = 20 + 5, M = 20 + 5;
int n, m, rmax, smax;
int a [N] [M], sum [N] [M];
int l [M], r [M];
int all = 0;
int sz [M];
int check (int w, int tot) {
	int cnt = 0;
	for (int i = 1; i <= tot; ++ i) {
		sz [i] = 0;
	}
	for (int i = 1; i <= n && cnt <= rmax; ++ i) {
		for (int j = 1; j <= tot; ++ j) {
			sz [j] += sum [i] [r [j]] - sum [i] [l [j] - 1];
		}
		for (int j = 1; j <= tot; ++ j) {
			if (sz [j] > w) {
				for (int k = 1; k <= tot; ++ k) {
					sz [k] = sum [i] [r [k]] - sum [i] [l [k] - 1];
				}
				++ cnt;
				break;
			}
		}
	}
	return cnt <= rmax;
}
int Search (int tot) {
	int L = 0, R = all, ans = all;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= tot; ++ j) {
			L = max (L, sum [i] [r [j]] - sum [i] [l [j] - 1]);
		}
	}
	while (L <= R) {
		int mid = (L + R) >> 1;
		if (check (mid, tot)) {
			ans = mid;
			R = mid - 1;
		}
		else { 
			L = mid + 1;
		}
	}
	return ans;
}
int main () {
	scanf ("%d %d %d %d", & n, & m, & rmax, & smax);
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			scanf ("%d", & a [i] [j]);
			all += a [i] [j];
		}
	}
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			sum [i] [j] = sum [i] [j - 1] + a [i] [j];
		}
	}
	int ans = all;
	for (int i = 0; i < (1 << (m - 1)); ++ i) {
		int tot = 1;
		l [1] = 1;
		for (int j = 1; j <= m - 1; ++ j) {
			if ((i >> (j - 1)) & 1) {
				r [tot] = j;
				++ tot;
				l [tot] = j + 1;
			}
		}
		r [tot] = m;
		if (tot > smax + 1) {
			continue;
		}
		ans = min (ans, Search (tot));
	}
	printf ("%d", ans);
	return 0;
}