本文主要是介绍poj 1050 To the Max (从O(N^6)到O(N^3))，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
求一个矩阵中的一个子矩阵，使得该子矩阵的所有元素的和最大，求出那个和。
解题思路：
最暴力的想法：枚举子矩阵的起点和终点，O(N^4)，对于每个子矩阵，求和，又是一个O(N^2) 对于N=100，N^6的复杂度太高。
我们可以用中间变量保存从1,1 到x，y的矩阵元素和，这样可以再O（1）的复杂度求出子矩阵的和，如图，红色部分的和就d[x][y]+d[x3][y3]-d[x1][y1]-d[x2][y2].
这样就把原先的O(N^6)降到了O(N^4)。
但是，对于这个题目O(N^4)复杂度也是比较大的。但是我们可以把复杂度降到O(N^3)。
第一步：我们枚举y坐标，这样我们的复杂度是O(N^2)。现在对于我们只要枚举横坐标就行，复杂度是O(N)。tem[j]表示在两个枚举的y坐标范围内，x坐标从1到j的和。
具体代码如下：
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int main()
{int n,m,i,j,t;int tmp[111],tem,a[111][111],sum[111][111];while(scanf("%d",&n)==1){memset(sum,0,sizeof(sum));for(i=1;i<=n;i++){for(j=1;j<=n;j++){scanf("%d",&a[i][j]);sum[i][j]=sum[i-1][j]+a[i][j];//同一列的前缀和}}int ans = -11111111;//y坐标从i到jfor(i=1;i<=n;i++){for(j=i;j<=n;j++){tmp[0]=0;//在i到j的范围内，x坐标的前缀和for(t=1;t<=n;t++){tem = sum[j][t]-sum[i-1][t];tmp[t] = max(tmp[t-1]+tem,tem);ans = max(ans,tmp[t]);}}}printf("%d\n",ans);}return 0;
}
这篇关于poj 1050 To the Max (从O(N^6)到O(N^3))的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
