- 最大子矩阵和
std.cpp
- 2025-4-6 17:03:13 @
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int a[N][N],b[N],dp[N],n;
int sub_sum(){
int ma=INT_MIN;
dp[1]=b[1]; //动态转移方程的边界
//求dp数组中最大连续子序列和
for(int i=2;i<=n;i++){
dp[i]=max(dp[i-1]+b[i],b[i]);
}
for(int i=1;i<=n;i++){ //求dp数组中的最大值
ma=max(ma,dp[i]);
}
return ma;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
//对二维数组状态压缩
int max_sum=a[1][1];
for(int i=1;i<=n;i++){
memset(b,0,sizeof(b));
//开始压缩
for(int j=i;j<=n;j++){
for(int z=1;z<=n;z++){
b[z]+=a[j][z];
}
//对b数组求最大连续子序列和
int s=sub_sum(); //写函数
if(s>max_sum){
max_sum=s;
}
}
}
//输出
cout<<max_sum<<endl;
return 0;
}
4 条评论
-
(未来の鳩(お互い))国贸单滢睿 LV 9 (37/37) @ 2025-4-7 18:08:59
?!老秦的题解·不敢吃
🤔 3 -
2025-4-6 21:31:09@
%%%%%%%%%
-
2025-4-6 17:08:03@
给老师点赞
👍 3 -
2025-4-6 17:05:17@
66666666666666666666666666666666666666666666666666666666666666666
👍 2❤️ 2🍋 2🌿 2👀 2
- 1
信息
- ID
- 2164
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 87
- 已通过
- 13
- 上传者