洛谷題目頁面傳送門 & CodeForces題目頁面傳送門
給定一個\(n\)行\(m\)列的矩陣，第\(i\)行\(j\)列為\(a_{i,j}\)，以及一個常數\(s\in\left[1,\left\lceil\dfrac{\min(n,m)}2\right\rceil\right]\)，求一個正整數對\((a,b)(a\in[s,n-s+1],b\in[s,m-s+1])\)使得\(f(a,b)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\max(0,s-(|i-a|+|j-b|))a_{i,j}\)最大，
\(n,m\in\left[1,10^3\right]\)，
將矩陣上每格對函式\(f\)值的貢獻的系數畫出來，會發現它是個斜著的正方形，中心系數等于\(s\)，往外\(1\)層系數減\(1\)，減到\(0\)為止，如下圖，
列舉中心點，可以得到\(\mathrm O(nm)\)個這樣的正方形，現在問題是怎么快速求出所有正方形的系數乘格子內的數之和，即所有中心點的函式值，假設我們已經知道了\(f(i,j)\)，現在想知道\(f(i,j+1)\)，不妨把這兩個正方形畫出來，看它們相差什么，
如上圖，是\(2\)個相鄰的\(s=3\)的正方形，紫色的數字是此格子內紅色系數減藍色系數，不難發現，左邊一半是一個差都是\(-1\)、高為\(s=3\)、直角頂點在底邊左側的等腰直角三角形，右邊一半是一個差都是\(1\)……底邊右側……，由此可以歸納出，設\(trl_{i,j}\)表示底邊中點為\((i,j)\)、高為\(s\)、直角頂點在底邊左側的等腰直角三角形內元素之和，\(trr_{i,j}\)表示……底邊右側……，則\(f(i,j)=f(i,j-1)-trl_{i,j-1}+trr_{i,j}\)，假設我們已經知道了\(trl,trr\)陣列，那么可以\(\forall i\in[s,n-s+1]\)，暴力用對角線前綴和\(\mathrm O(s)\)求出\(f(i,s)\)，然后\(\forall i\in[s,n-s+1],\forall j\in(s,m-s+1]\)，用上面那個關系式遞推求出\(f(i,j)\)，總復雜度為\(\mathrm O(nm)\)，
現在問題轉化為怎么快速求出\(trl,trr\)陣列，以\(trl\)為例，先畫出相鄰兩個三角形，
如上圖，是兩個相鄰的\(s=3\)的三角形，紫色的數字是此格子內紅色系數減藍色系數，又不難發現，左邊的三角形輪廓的差都是\(-1\)，右邊一列的差都是\(1\)，這個輪廓的和和列的和可以維護列前綴和\(Sum1\)、副對角線前綴和\(Sum2\)（在同一條副對角線上當且僅當行列和相等）、主對角線前綴和\(Sum3\)（在同一條主對角線上當且僅當行列差相等）搞定，于是就有了一個\(trl_{i,j},trl_{i,j-1}\)的關系式，那么可以\(\forall i\in[s,n-s+1]\)，暴力用列前綴和\(\mathrm O(s)\)求出\(trl_{i,s}\)，然后\(\forall i\in[s,n-s+1],\forall j\in(s,m]\)，用關系式遞推求出\(trl_{i,j}\)，總復雜度為\(\mathrm O(nm)\)，\(trr\)求法類似，
\(\mathrm O(nm)\)與處理完\(3\)個前綴和，\(trl,trr\)就可以\(\mathrm O(nm)\)求出來了，那么\(f\)也可以\(\mathrm O(nm)\)求出來了，最后找最大值即可，總復雜度\(\mathrm O(nm)\)，
下面貼代碼：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define X first
#define Y second
const int N=1000,M=1000;
int n/*矩陣行數*/,m/*矩陣列數*/,s/*常數*/;
int a[N+1][M+1];//矩陣
int Sum1[M+1][N+1]/*列前綴和*/,Sum2[N+M+1][M+1]/*副對角線前綴和*/,Sum3[2*N+1][M+1]/*主對角線前綴和，由于行列差可能是負數，所以平移max(n,m)個單位*/;
int sum1(int x,int l,int r){return l>r?0:Sum1[x][r]-Sum1[x][l-1];}//列區間和
int sum2(int x,int l,int r){return l>r?0:Sum2[x][r]-Sum2[x][l-1];}//副對角線區間和
int sum3(int x,int l,int r){return l>r?0:Sum3[x+max(n,m)][r]-Sum3[x+max(n,m)][l-1];}//主對角線區間和
int trl[N+1][M+1],trr[N+1][M+1];//朝左、朝右三角形
int rhm[N+1][M+1];//正方形，即f函式
signed main(){
cin>>n>>m>>s;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%lld",a[i]+j);
//預處理前綴和開始
for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)Sum1[i][j]=Sum1[i][j-1]+a[j][i];
for(int i=1;i<=n+m;i++)for(int j=1;j<=n;j++)Sum2[i][j]=Sum2[i][j-1]+(1<=i-j&&i-j<=m?a[j][i-j]:0);
for(int i=-max(n,m);i<=max(n,m);i++)for(int j=1;j<=n;j++)Sum3[i+max(n,m)][j]=Sum3[i+max(n,m)][j-1]+(1<=j+i&&j+i<=m?a[j][j+i]:0);
//預處理前綴和結束
for(int i=s;i<=n-s+1;i++){//算trl
for(int j=1;j<=s;j++)trl[i][s]+=sum1(j,i-j+1,i+j-1);//暴力算邊上的trl
for(int j=s+1;j<=m;j++)trl[i][j]=trl[i][j-1]+sum1(j,i-s+1,i+s-1)-sum2(i+j-s,i-s+1,i)-sum3(j-s-i,i+1,i+s-1);//用關系式遞推其他trl
}
for(int i=s;i<=n-s+1;i++){//算trr，與trl類似
for(int j=m;j>=m-s+1;j--)trr[i][m-s+1]+=sum1(j,i-(m-j+1)+1,i+(m-j+1)-1);
for(int j=m-s;j;j--)trr[i][j]=trr[i][j+1]+sum1(j,i-s+1,i+s-1)-sum3(j+s-i,i-s+1,i)-sum2(i+j+s,i+1,i+s-1);
}
// for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)printf("tr(%lld,%lld)=(%lld,%lld)\n",i,j,trl[i][j],trr[i][j]);
for(int i=s;i<=n-s+1;i++){//算rhm
for(int j=0;j<s;j++)rhm[i][s]+=(s-j)*(sum2(i-j+s,i-j,i)+sum3(s-(i+j),i+1,i+j)+sum2(i+j+s,i,i+j-1)+sum3(s-(i-j),i-j+1,i-1));//暴力算邊上的rhm
for(int j=s+1;j<=m-s+1;j++)rhm[i][j]=rhm[i][j-1]+trr[i][j]-trl[i][j-1];//用關系式遞推其他rhm
}
// for(int i=s;i<=n-s+1;i++)for(int j=s;j<=m-s+1;j++)printf("rhm[%lld][%lld]=%lld\n",i,j,rhm[i][j]);
pair<int,pair<int,int> > mx(0,mp(0,0));
for(int i=s;i<=n-s+1;i++)for(int j=s;j<=m-s+1;j++)mx=max(mx,mp(rhm[i][j],mp(i,j)));//找最大值
cout<<mx.Y.X<<" "<<mx.Y.Y;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/71515.html
標籤：C++
上一篇：KMP演算法