洛谷P1719 最大加权矩形 （DP/二维前缀和）

题目描述也没啥好说的，就是给你个你n*n的矩形（带权），求其中最大权值的子矩阵。

首先比较好想的就是二维前缀和，n<=120，所以可以用暴力。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 int n,f[130][130],ans=-0x3f3f3f3f;

 4 //n^4爆搜

 5 int main(){

 6     scanf("%d",&n);

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

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

 9             int x;

10             scanf("%d",&x);

11             f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+x;

12         }

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

14         for(int k1=1;k1<=i;k1++)

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

16                 for(int k2=1;k2<=j;k2++){

17                     int sum=f[i][j]-f[i-k1][j]-f[i][j-k2]+f[i-k1][j-k2];

18                     ans=max(ans,sum);

19                 }

20     cout<<ans;

21 }

当然有更优的解法，我们可以类比P1115最大子段和，把矩形从二维压缩到一维，然后DP，统计答案就行了。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=150;

 4 int n,m,a[N][N];

 5 int temp[N],dp[N],ans=-0x3f3f3f3f;

 6

 7 void getsum(){

 8     memset(dp,0,sizeof(dp));

 9     for(int i=1;i<=n;i++){//类似于求一维的最大子段和

10         dp[i]=max(dp[i],dp[i-1]+temp[i]);

11         ans=max(ans,dp[i]);

12     }

13 }

14

15 void solve(){

16     for(int i=1;i<=n;i++){//矩阵压缩

17         memset(temp,0,sizeof(temp));

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

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

20                 temp[k]+=a[j][k];

21             }

22             getsum();

23         }

24     }

25 }

26

27 int main(){

28     scanf("%d",&n);

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

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

31             scanf("%d",&a[i][j]);

32     solve();

33     cout<<ans;

34 }

洛谷P1719 最大加权矩形 （DP/二维前缀和）的相关教程结束。