左上角"/>
快速提升代码能力(3)矩阵的左上角
从零起步看算法 (第三天 4.8)
//q4 求最大子阵
一.开始理解错了题目意思,简单的想成了行的一维,变换起始点的最大值。
错误的路上,看到了一些不一样的风景。
比如:
1.起始点变化的总结,双重循环的初始点使用。
最大子段和问题的递推公式是 b[j]=max{b[j-1]+a[j], a[j]},
2.在标尺比较大小的方法中,要注意回溯。
#include<iostream>
#include<string>
#include<assert.h>
#include<stdio.h>
#include<cstring>
using namespace std;
#define MAXN 50
int f(int b[][MAXN],int x,int y){//int sum=0;
// int array[MAXN];
// memset(array,0,sizeof(array));
// for(int i=0;i<x;i++){//以行为单位,形成和
// for(int j=0;j<y;j++){
// array[i]+=b[i][j];
// }
// } // for(int f=0;f<x;f++){//调试
// cout<<array[f]<<endl;
// }//暴力枚举所有的子矩阵 for(int i=0;i<x;i++){for(int j=i;j<y;j++)
} int sum=0;int max=array[0];for(int m=0;m<x;m++){//起始点变换的数组比较 for(int k=m;k<x;k++){sum+=array[k];if(sum>max)max=sum; }sum=0;//回溯 }return max;
}
int main(){int a[MAXN][MAXN];memset(a,0,sizeof(a));int x=0,y=0;cin>>x>>y;//x为行,y为列 assert(x>=1&&x<=50&&y>=1&&y<=50);for(int i=0;i<x;i++){//样例输入 for(int j=0;j<y;j++){scanf("%d",&a[i][j]);if(a[i][j]<-1000||a[i][j]>1000)return 0; }}cout<<f(a,x,y)<<endl;return 0;
}
二.网上学习:列减方法(晕晕乎乎,还没ac)
有些地方还是可以学习的
数组可以开大一点。
#include<iostream>
#include<string>
#include<assert.h>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 50+5int f(int b[][MAXN],int x,int y){
//暴力枚举所有矩阵int c[x][y];memset(c,0,sizeof(c));//列的上下清算for(int j=0;j<y;j++){c[0][j]=b[0][j];}for(int i=1;i<x;i++){for(int j=0;j<y;j++){c[i][j]=b[i][j]+b[i-1][j];}} //表尺法,找最大值 int sum[y];int max=0;memset(sum,0,sizeof(sum));//回归一维 //行的寻找for(int i=0;i<x;i++){for(int j=i;j<x;j++){//列的扫描,第i行,和第j行之间列的差for(int m=0;m<y;m++){//第m行列的总和 if(i==0)sum[m]=c[j][m];//第一行elsesum[m]=c[j][m]-c[i-1][m]; }//表尺法,找最大值 sort(sum,sum+y);max=sum[y-1];int add=0; for(int k=0;k<y;k++) {for(int h=k;h<y;h++){add+=sum[k];if(max<add)max=add;} add=0;//回溯 } }} return max; }int main(){int a[MAXN][MAXN];memset(a,0,sizeof(a));int x=0,y=0;cin>>x>>y;//x为行,y为列 assert(x>=1&&x<=50&&y>=1&&y<=50);for(int i=0;i<x;i++){//样例输入 for(int j=0;j<y;j++){scanf("%d",&a[i][j]);if(a[i][j]<-1000||a[i][j]>1000)return 0; }}cout<<f(a,x,y)<<endl;return 0;
}
三.最大子矩阵枚举法
#include<iostream>
#include <cstring>
using namespace std;
int max(int a,int b){
return a>b?a:b;}
int main(){
int n,m,i,j,k,MAX=-9999,a[51]
[51],dp[51][51];
cin>>n>>m;//行和列memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));for(i = 1; i <= n; ++i){
for(j = 1; j <= m; ++j)
{
cin>>a[i][j];
dp[i][j]=dp[i-1][j]+dp[i][j-1]+a[i][j]-dp[i-1][j-1];
}
}
for(i=1;i<=n;++i){
for(j=1;j<=m;++j){
for(int p=1;p<=i;++p){
for(int q=1;q<=j;++q){
MAX =max(dp[i][j]-dp[i][q-1]-dp[p-1][j]+dp[p-1][q-1],MAX);
}
}
}
}
cout<<MAX;
return 0;
}
不是很懂。
四.本题重点:暴力枚举法
1.注意理解思路,将矩阵的左上角,和右下角为暴力枚举的突破点。
2.多重枚举,要注意细节,字母容易打错。
3.求最大值的标尺值的设立,要注意。
学会分析问题的角度:矩阵可以用两个角的坐标来限制
#include<iostream>
#include<string>
#include<assert.h>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 50+5
int f(int a[][MAXN],int x,int y){int max=-1009;//求最大值,设标尺//利用矩阵的两的角的坐标来限制矩阵 for(int i=0;i<x;i++){for(int j=0;j<y;j++){for(int p=x;p>i;--p){for(int q=y;q>j;--q){int sum=0;for(int m=i;m<p;m++){for(int k=j;k<q;k++){sum+=a[m][k]; } }if(sum>max)max=sum;}}}}return max;
} int main(){int a[MAXN][MAXN];memset(a,0,sizeof(a));int x=0,y=0;cin>>x>>y;//x为行,y为列 assert(x>=1&&x<=50&&y>=1&&y<=50);for(int i=0;i<x;i++){//样例输入 for(int j=0;j<y;j++){scanf("%d",&a[i][j]);if(a[i][j]<-1000||a[i][j]>1000)return 0; }}cout<<f(a,x,y)<<endl;return 0;
}
更多推荐
快速提升代码能力(3)矩阵的左上角
发布评论