最大化（矩阵前缀和）

矩阵前缀和+神奇的剪枝

矩阵前缀和

如图，a[2][2]的前缀和就是2+3+2+7，a[1][4]的前缀和就是2+3+4+8
以此类推，每一个坐标的前缀和，都是该坐标到矩阵左上角的数字之和；
这样，任意子矩阵的数字和，可以在O（1）时间内查询；
代码实现

 for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]+=b[i][j-1];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]+=b[i-1][j];//计算前缀和

int js(int i,int j,int l,int r)//i,j为查询矩阵左上角顶点，l,r为右下角顶点
{sum=b[l][r]-b[i-1][r]-b[l][j-1]+b[i-1][j-1];
}//查询任意矩阵数字和

让原本不是十分优秀的算法跑的还挺快。。。

输入

3 2
4 0
-10 8
-2 -2

输出
4

#include
#include
using namespace std;bool js(int i,int j,int l,int r)
{return b[l][r]-b[i-1][r]-b[l][j-1]+b[i-1][j-1]>0;
}bool check(int x)
{for(int i=1;i<=n;i++){if(x%i)continue;int ll=i,rr=x/i;for(int k=1;k+ll-1<=n;k++)for(int h=1;h+rr-1<=n;h++)if(js(k,h,k+ll-1,h+rr-1))return 1;}for(int i=1;i<=n;i++)pr[i*x]=1;return 0;
}int main()
{scanf("%d%d",&n,&m)for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",a[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]+=b[i][j-1];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)b[i][j]+=b[i-1][j];for(int i=1;i<=n*m;i++){if(!pi[i])if(check(i))ans=i;}printf("%d",ans);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！