[ABC311G] One More Grid Task
题目信息
题面翻译
给你一个 \(n\times m\) 的矩阵 \(a\)，求：
\[\max_{1\leq l_1\leq r_1\leq n,1\leq l_2\leq r_2\leq m} (\sum_{l_1\leq i\leq r_1,l_2\leq j\leq r_2}a_{i,j} \times\min_{l_1\leq i\leq r_1,l_2\leq j\leq r_2}a_{i,j}) \]题目描述
$ N\ \times\ M $ のグリッドがあり、上から $ i $ 行目、左から $ j $ 列目のマス $ (i,j) $ には非負整数 $ A_{i,j} $ が書かれています。
このグリッドのうち長方領域をひとつ選び、それを $ R $ とします。
厳密には、長方領域は以下の手順で選ばれます。
- $ 1\ \le\ l_x\ \le\ r_x\ \le\ N,\ 1\ \le\ l_y\ \le\ r_y\ \le\ M $ なる整数 $ l_x,\ r_x,\ l_y,\ r_y $ を選ぶ。
- このとき、整数 $ i,j $ が $ l_x\ \le\ i\ \le\ r_x $ かつ $ l_y\ \le\ j\ \le\ r_y $ を満たす、またその時に限って、マス $ (i,j) $ は $ R $ に含まれる。
適切に $ R $ を選ぶことによって、 $ f(R)\ = $ ( $ R $ 内のマスに書かれた整数の総和 ) $ \times $ ( $ R $ 内のマスに書かれた整数の最小値 ) として達成可能な最大値を求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
$ N $ $ M $ $ A_{1,1} $ $ A_{1,2} $ $ \dots $ $ A_{1,M} $ $ A_{2,1} $ $ A_{2,2} $ $ \dots $ $ A_{2,M} $ $ \vdots $ $ A_{N,1} $ $ A_{N,2} $ $ \dots $ $ A_{N,M} $
输出格式
答えを整数として出力せよ。
样例 #1
样例输入 #1
3 3
5 4 3
4 3 2
3 2 1
样例输出 #1
48
样例 #2
样例输入 #2
4 5
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4
样例输出 #2
231
样例 #3
样例输入 #3
6 6
1 300 300 300 300 300
300 1 300 300 300 300
300 300 1 300 300 300
300 300 300 1 300 300
300 300 300 300 1 300
300 300 300 300 300 1
样例输出 #3
810000
提示
制約
- 入力は全て整数
- $ 1\ \le\ N,M\ \le\ 300 $
- $ 1\ \le\ A_{i,j}\ \le\ 300 $
Sample Explanation 1
左上がマス $ (1,1) $ 、右下がマス $ (2,2) $ の長方領域を選ぶことで、 $ f(R)\ =\ (5+4+4+3)\ \times\ \min(5,4,4,3)\ =\ 48 $ が達成でき、これが達成可能な最大値です。
题目思路
算法一
我们可以考虑直接枚举左上角，枚举右下角，暴力求和以及暴力求最小值。
时间复杂度：\(O(n^3m^3)\).
算法二
算法一显然不行。我们可以提前预处理，用上数据结构（比如说树状数组、线段树树），直接求最小值和和。
时间复杂度：\(O(n^2m^2\log n\log m)\)。
算法三
算法二显然也不行。考虑优化。
我们知道：任何矩阵的问题都可以压缩成一维问题。即枚举上届、枚举下届，求方案数。
预处理后，我们可以记录 \(left_i\)、\(right_i\) 分别代表能延伸的最左边，能延伸的最右边。
直接使用单调栈维护即可。
时间复杂度：\(O(n^2m\log n)\)。
代码
// LUOGU_RID: 161862093
#include<bits/stdc++.h>
#define int long long
#define left _zqh_
#define right flying_hq
using namespace std;
const int MAXN = 320;
const int LOGN = log2(MAXN)+5;
int n,m,matrix[MAXN][MAXN],ans;
void read(int &x){
x = 0;int p = 1;char ch;
do{
ch = getchar();
if(ch=='-') p = -1;
}while(!isdigit(ch));
while(isdigit(ch)){
x*=10;
x+=ch-'0';
ch = getchar();
}
x*=p;
}
int sum[MAXN][MAXN],now[MAXN],left[MAXN],right[MAXN],q[MAXN],minn[MAXN];
class Segmenttree{
private:
struct segment{
int l,r,min=0X3F3F3F3F;
}tree[MAXN<<3];
void pushup(int id){
tree[id].min = min(tree[id*2].min,tree[id*2+1].min);
}
public:
void build(int k,int l,int r){
tree[k].l = l;
tree[k].r = r;
if(l==r) return;
int mid = (l+r)>>1;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
}
void change(int k,int p,int q){
if(tree[k].l>p||tree[k].r<p) return;
if(tree[k].l>=p&&tree[k].r<=p){
tree[k].min = q;
return;
}
change(k*2,p,q);
change(k*2+1,p,q);
pushup(k);
}
int getmin(int k,int l,int r){
if(tree[k].l>r||tree[k].r<l) return 0x3f3f3f3f;
if(tree[k].l>=l&&tree[k].r<=r){
return tree[k].min;
}
return min(getmin(k*2,l,r),getmin(k*2+1,l,r));
}
}tree[MAXN];
signed main(){
read(n);read(m);
for(int i = 1;i<=m;i++) tree[i].build(1,1,n);
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
read(matrix[i][j]);
sum[i][j] = sum[i-1][j]+matrix[i][j];
tree[j].change(1,i,matrix[i][j]);
}
}
for(int i = 1;i<=n;i++){
for(int j = i;j<=n;j++){
if(i == 1&&j== 2){
int k = 0;
}
for(int k = 1;k<=m;k++){
now[k] = sum[j][k]-sum[i-1][k];
q[k] = q[k-1]+now[k];
minn[k] = tree[k].getmin(1,i,j);
}
stack<pair<int,int>> st;
for(int k = 1;k<=m;k++){
while(!st.empty()&&st.top().second>=minn[k]) st.pop();
if(st.empty()){
left[k] = 1;
}else{
left[k] = st.top().first+1;
}
st.push({k,minn[k]});
}
while(!st.empty()){
st.pop();
}
for(int k = m;k>=1;k--){
while(!st.empty()&&st.top().second>=minn[k]) st.pop();
if(st.empty()){
right[k] = m;
}else{
right[k] = st.top().first-1;
}
st.push({k,minn[k]});
}
for(int k = 1;k<=m;k++){
ans = max(ans,(q[right[k]]-q[left[k]-1])*minn[k]);
}
}
}
printf("%lld",ans);
return 0;
}
tag
Atcoder、题解
单调栈、线段树、树状数组、数据结构