题解 P1719 【最大加权矩形】
先讲一下60分做法
看到这道题，我第一眼就想到，可以暴力枚举，于是我运用了前缀和，将原本的六重循环优化了一下（不算求和部分）先贴一下代码
#include <iostream>
#include <cstdio>
using namespace std;
int matrix[311][311],a[311][311];
int main()
{
//freopen("max.in","r",stdin);
//freopen("max.out","w",stdout);
int i,j,k,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
matrix[i][j]=matrix[i][j-1]+a[i][j];
}
}
int ans=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
for(int xx=1;i+xx-1<=n;xx++)
{
for(int yy=1;j+yy-1<=n;yy++)
{
int num=0;
int s1=i+xx-1,s2=j+yy-1;
for(int xun=j;xun<=s2;xun++)
num+=matrix[xun][s1];
ans=max(ans,num);
}
}
}
}
printf("%d",ans);
return 0;
}但是，这样子做会超时4个点，我们应该怎么办呢？
此时，我想到了一个脑残的方法，再来一个前缀和数组，将原来的matrix数组定义为（1,1）~（x,y）这个矩阵的和，新增的数组，用来表示每一行的前缀和
于是，我们修改一下代码
#include <iostream>
#include <cstdio>
using namespace std;
int matrix[311][311],duan[311][311],a[311][311];
int main()
{
freopen("max.in","r",stdin);
freopen("max.out","w",stdout);
int i,j,k,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
duan[i][j]=duan[i][j-1]+a[i][j];
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
matrix[i][j]=matrix[i-1][j]+duan[i][j];
}
}
int ans=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++) //枚举这个矩阵的起始坐标
{
for(int xx=1;i+xx-1<=n;xx++)//这个矩阵的x坐标长多少
{
for(int yy=1;j+yy-1<=n;yy++)//这个矩阵的y坐标长多少
{
int num=0;
int s1=i+xx-1,s2=j+yy-1;
ans=max(ans,matrix[s1][s2]-(matrix[s1][j-1]-matrix[i-1][j-1])-matrix[i-1][s2]);//求出当前枚举出的这个矩阵和是多少
}
}
}
}
printf("%d",ans);//输出答案
while(1);//反抄袭
return 0;
}