归并排序
No.1 (逆序数)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include<bits/stdc++.h> typedef long long ll; using namespace std; ll sum,a[520][520],dp[520]; ll N,M,mas=-1,temp; ll maxsub() { ll mas=0,t=0; for(int i=0;i<M;i++) { if(t>0)t+=dp[i]; else t=dp[i]; if(t>mas)mas=t; } return mas; } int main() { cin>>M>>N; for(int i=0;i<N;i++) for(int j=0;j<M;j++) cin>>a[i][j]; for(int i=0;i<N;i++) { memset(dp,0,sizeof(dp)); for(int j=i;j<N;j++) { for(int k=0;k<M;k++) dp[k]+=a[j][k]; temp=maxsub(); if(temp>mas)mas=temp; } } if(mas>=0)cout<<mas<<endl; else cout<<0<<endl; return 0; } |