TIOJ 1277 . 俄羅斯娃娃－續

題目鏈接:https://tioj.ck.tp.edu.tw/problems/1277

這題是最大子矩陣和

讀板中講義的時候跳過

過了很久才回來解掉

其實這題本質上是最大子序列和的延伸

也就是將最大子矩陣和轉換成最大子序列和

輸入時把整個矩陣的直向的前綴和記錄下來

如範例中的

3

1 -1 2

-8 3 -9

3 -2 3

將其轉換為

1 -1 2

-7 2 -7

-4 0 -4

因為他是前綴和所以我們可知

\[v_{ij}+v_{i+1j}+v_{i+2j}+........+v_{kj}=sum_{kj}-sum_{i-1j}\]

所以我們可以窮舉\(v_{ij}\)的所有情況

將矩陣和壓為一維的序列和

再求最大子序列和就可以了

以下為code

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

int main()

{

AC

int n;

ll r=0;

cin>>n;

vector<vector<ll>> v(n+1,vector<ll>(n+1));

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

{

int t;

cin>>t;

v[i][j]=v[i-1][j]+t;

}

for(int i=1;i<=n;i++)

{

for(int j=i;j<=n;j++)

{

ll tmp=0;

for(int k=1;k<=n;k++)

{

if(tmp>=0) tmp+=v[j][k]-v[i-1][k];

if(tmp<0) tmp=v[j][k]-v[i-1][k];

r=max(r,tmp);

}

}

}

cout<<r<<'\n';

}