1.处理出
f
[
i
]
[
j
]
[
k
]
f[i][j][k]
f[i][j][k]，表示第
i
i
i行从第
j
j
j列到第
k
k
k列里有多少个
0
0
0
2.容易想到
O
(
n
4
)
O(n^4)
O(n4)的做法，枚举矩形的上边在第
i
i
i行的第
j
j
j列到第
k
k
k列，下边在第
s
s
s行
但是题目最多只能
O
(
n
3
)
O(n^3)
O(n3)
3.考虑优化，将枚举上边和下边所在行的时间复杂度
O
(
n
2
)
O(n^2)
O(n2)优化成
O
(
n
)
O(n)
O(n)
把矩形分成3个部分，上边，中间部分，下边
假设枚举到了第
i
i
i 行，
m
n
mn
mn 表示前
i
−
1
i-1
i−1 行 上边+中间部分 的最小值
m
n
mn
mn 可以再通过一个变量
s
s
s 来维护
s
s
s表示
a
a
a 取
5
5
5 时中间部分的价值
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)scanf("%1d", &a[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
l[i][j] = l[i][j - 1] + !a[i][j];
int res = 1e9;
for (int i = 2; i < m; i++) {
for (int j = i + 1; j < m; j++) {
int mn = l[1][j] - l[1][i - 1];
int s = 0;
for (int k = 2; k < 5; k++)s += !a[k][i - 1] + !a[k][j + 1] + (j - i + 1 - (l[k][j] - l[k][i - 1]));
mn += s;
for (int k = 5; k <= n; k++) {
res = min(res, l[k][j] - l[k][i - 1] + mn);
s = s - !a[k - 3][i - 1] - !a[k - 3][j + 1] - (j - i + 1 - (l[k - 3][j] - l[k - 3][i - 1]));
mn = min(mn, l[k - 3][j] - l[k - 3][i - 1] + s);
mn += (j - i + 1 - (l[k][j] - l[k][i - 1])) + !a[k][i - 1] + !a[k][j + 1];
s += (j - i + 1 - (l[k][j] - l[k][i - 1])) + !a[k][i - 1] + !a[k][j + 1];
}
}
}
cout << res << endl;
}
