矩阵元素相乘

发布于:2021-06-19 14:52:09

题目描述


A[n,m]是一个n行m列的矩阵,a[i,j]表示A的第i行j列的元素,定义x[i,j]为A的第i行和第j列除了a[i,j]之外所有元素(共n+m-2个)的乘积,即x[i,j]=a[i,1]*a[i,2]*...*a[i,j-1]*...*a[i,m]*a[1,j]*a[2,j]...*a[i-1,j]*a[i+1,j]...*a[n,j],现输入非负整形的矩阵A[n,m],求MAX(x[i,j]),即所有的x[i,j]中的最大值。


IDEA
第一想法就是用除法,行的积除以该数*列的积除以该数,单数但是会出现除0异常


第二想法就是对每个数按题目给定的方法计算,但是复杂度为三层循环


第三想法,用动态规划,两个规划矩阵,分别存储除该数以为的行积,列积。开始遍历存的数是从是开是该数之前的积,后一次倒序遍历乘上该数之后的积。复杂度为n*m


CODE


#include
#include
using namespace std;
int main(){
int n,m;
while(cin>>n>>m){
vector > vec(n,vector(m,0));
vector > p1(n,vector(m,1));
vector > p2(n,vector(m,1));
for(int i=0;i for(int j=0;j cin>>vec[i][j];
if(j>0)
p1[i][j]=p1[i][j-1]*vec[i][j-1];
if(i>0)
p2[i][j]=p2[i-1][j]*vec[i-1][j];
}
}
int temp;
for(int i=0;i temp=1;
for(int j=m-1;j>=0;j--){
p1[i][j]=p1[i][j]*temp;
temp*=vec[i][j];
}
}
for(int i=0;i temp=1;
for(int j=n-1;j>=0;j--){
p2[j][i]=p2[j][i]*temp;
temp*=vec[j][i];
}
}
int res=0;
for(int i=0;i for(int j=0;j res=max(res,p1[i][j]*p2[i][j]);
}
}
cout< }
return 0;
}





相关推荐

最新更新

猜你喜欢