在枚举的情况下双指针
O(N^3)
- 枚举所有列的组合
- 每次加上这个范围内同一列的所有元素,转化成了普通的双指针
- 至于怎么快速加上同一列某一范围内的元素,可以使用前缀和
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int g[N][N];
int n, m, k;
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
cin >> g[i][j];
g[i][j] += g[i - 1][j]; //求出每列的前缀和,与行无关
}
}
int res = INT_MAX;
for (int x = 1; x <= n; x ++) //枚举列的组合
for (int y = x; y <= n; y ++)
for (int i = 1, j = 1, sum = 0; i <= m; i ++)//对行用双指针
{
sum += g[y][i] - g[x - 1][i]; //扩大
while (sum - g[y][j] + g[x - 1][j] >= k)
{
sum -= g[y][j] - g[x - 1][j];
j ++; //收缩
}
if (sum >= k) //更新符合条件的面积
res = min(res, (y - x + 1) * (i - j + 1));
}
if (res == INT_MAX) res = -1;
cout << res << endl;
return 0;
}
普通的优化了一点的暴力,用到了二维前缀和
O(N^4)可能样例不多
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int mp[N][N];
int main()
{
int n,m,k;cin >> n >> m >> k;
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= m;j ++){
cin >> mp[i][j];
mp[i][j] += mp[i-1][j] + mp[i][j-1] - mp[i-1][j-1];
}
}
if(mp[n][m] < k){
cout << -1 << endl;
return 0;
}
int min_S = 1e9;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
{
int x = i,y = j;
while(x <= n && y <= m){
int sum = mp[x][y] - mp[x][j-1] - mp[i-1][y] + mp[i-1][j-1];
int S = (x - i + 1) * (y - j + 1);
if(sum < k && y != m){
y++;
}
else {
if(sum >= k)min_S = min(S,min_S);
y = j;
x++;
}
}
}
cout << min_S << endl;
}