生活随笔
收集整理的這篇文章主要介紹了
1282：最大子矩阵《信息学奥赛一本通》
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
/*
1282：最大子矩陣
http://ybt.ssoier.cn:8088/problem_show.php?pid=1282
P2331 [SCOI2005]最大子矩陣
https://www.luogu.org/problemnew/show/P2331
*/
#include <iostream>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
int a[201][201],sum[201][201];
int temp[200+1];
int n;void solve()
{int i,j,k,max=-INT_MAX,sumall;for(i=0;i<=n;i++) for(j=i+1;j<=n;j++) //從i行到j(luò)行{for(k=1;k<=n;k++) //該循環(huán)求出i到j(luò)行第k列的和{temp[k]=sum[j][k]-sum[i][k];cout<<"i1="<<i<<" j="<<j<<" k="<<k<<" temp["<<k<<"]="<<temp[k]<<endl;}cout<<endl;//cout<<"********************************************"<<endl; sumall=0;for(k=1;k<=n;k++) //與最大子序列和一樣，找到最大值{sumall+=temp[k];if(sumall>max) //記錄最大值 max=sumall;if(sumall<0)sumall=0;}cout<<"i2="<<i<<" max1="<<max<<endl;cout<<"????????????????????????????????"<<endl<<endl;}cout<<max<<endl;
}void init()
{int i,j;cin>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>a[i][j];//顯示輸入的矩陣 for(i=1;i<=n;i++){for(j=1;j<=n;j++)cout<<a[i][j]<<" ";cout<<endl;}cout<<"------------------------"<<endl; for(i=1;i<=n;i++) // sum[i,j]表示矩陣第j列前i個元素的和， for(j=1;j<=n;j++)sum[i][j]=sum[i-1][j]+a[i][j];//壓縮數(shù)據(jù)for(i=1;i<=n;i++){for(j=1;j<=n;j++)cout<<sum[i][j]<<" ";cout<<endl;}
}int main()
{freopen("Matrix2d.in","r",stdin);freopen("Matrix2d.out","w",stdout); init();solve();return 0;
}
?
總結(jié)
以上是生活随笔為你收集整理的1282：最大子矩阵《信息学奥赛一本通》的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
