SG2. 矩阵元素相乘
描述
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]中的最大值。输入描述
第一行两个整数n和m。之后n行输入矩阵,均为非负整数。输出描述
一行输出答案。示例1
输入:
3 5 5 1 8 5 2 1 3 10 3 3 7 8 5 5 16
输出:
358400
C 解法, 执行用时: 2ms, 内存消耗: 312KB, 提交时间: 2021-09-23
#include <stdio.h> #include <limits.h> int main() { int n,m; while(scanf("%d %d",&n,&m)!=EOF) { int arr[n][m]; int max=INT_MIN; for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d",&arr[i][j]); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { int sum=1; for(int k=0;k<n;k++) if(k!=i) sum*=arr[k][j]; for(int k=0;k<m;k++) if(k!=j) sum*=arr[i][k]; if(sum>max) max=sum; } } printf("%d\n",max); } return 0; }
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-09-08
#include <iostream> #include <vector> using namespace std; long shuzi(vector< vector<int> > v,int i,int j) { int x,y; long sum = 1; for(x=0;x<v.size();x++) { if(x!=i) { sum *= v[x][j]; } } for(y=0;y<v[0].size();y++) { if(y!=j) { sum *= v[i][y]; } } return sum; } int main() { int n,m; while(cin>>n>>m) { vector< vector<int> > v(n); int temp; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cin>>temp; v[i].push_back(temp); } } long max = 0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(max < shuzi(v,i,j)) { max = shuzi(v,i,j); } } } cout<<max<<endl; } }
C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-05-15
#include<stdio.h> int main(){ int n,m,i,j,k; while(scanf("%d %d",&n,&m)==2){ long long t,max=0; int a[n][m]; for(i=0;i<n;i++) for(j=0;j<m;j++) scanf("%d",&a[i][j]); for(i=0;i<n;i++){ for(j=0;j<m;j++){ t=1; for(k=0;k<j;k++) t=t*a[i][k]; for(k=j+1;k<m;k++) t=t*a[i][k]; for(k=0;k<i;k++) t=t*a[k][j]; for(k=i+1;k<n;k++) t=t*a[k][j]; if(t>max) max=t; } } printf("%lld\n",max);} return 0; }
C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2018-09-11
#include <stdio.h> int main() { int m,n,i,j,p,q; long A[10000][10000]; long X[10000][10000]; long max_x,temp1; while(scanf("%d %d",&m, &n) != EOF) { for (i=0;i<m;i++) { for(j=0;j<n-1;j++) { scanf("%d ",&A[i][j]); } scanf("%d\n",&A[i][j]); } max_x=0; for(i=0;i<m;i++) { for(j=0;j<n;j++) { temp1=1; for(p=0;p<j;p++) temp1=temp1*A[i][p]; for(p=j+1;p<n;p++) temp1=temp1*A[i][p]; for(p=0;p<i;p++) temp1=temp1*A[p][j]; for(p=i+1;p<m;p++) temp1=temp1*A[p][j]; // temp1=temp1/A[i][j]/A[i][j]; X[i][j]=temp1; if(X[i][j]>max_x) max_x=X[i][j]; } } printf("%d\n",max_x); } return 0; }
C++ 解法, 执行用时: 2ms, 内存消耗: 380KB, 提交时间: 2021-05-29
#include <iostream> #include <vector> using namespace std; int main(){ int n,m; while (cin >> n >> m){ vector<vector<int>> A(n, vector<int>(m, 0)); vector<int> row(n); vector<int> col(m); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> A[i][j]; A[i][j] = A[i][j] == 0 ? -1 : A[i][j]; row[i] = j==0 ? A[i][j] : row[i] * A[i][j]; col[j] = i==0 ? A[i][j] : col[j] * A[i][j]; } } int res = 0; //cout << col[2] << endl; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ res = max(res, row[i] * col[j] / A[i][j] / A[i][j]); } } cout << res << endl; } return 0; }