首页 > 代码库 > POJ 1050 To the Max 枚举+dp
POJ 1050 To the Max 枚举+dp
大致题意：
求最大子矩阵和
分析：
一开始想复杂了，推出了一个状态方程：d[i][j]=max(d[i][j-1]+…,d[i-1][j]+…)。写着写着发现上式省略的部分记录起来很麻烦。
后来发现n最大100，干脆直接枚举行，先枚举所有行的情况，然后将矩阵压缩为数列，最后用最大子段和求解。写着写着感觉就会超时，毕竟出现了四层循环嵌套。结果过了，说明测试数据有点水。
#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>using namespace std;const int maxn=100+5;const int INF=1e7;int a[maxn][maxn];int b[maxn];int ans;int main(){ int n; scanf("%d",&n); for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d",&a[i][j]); for(int i=0; i<n; i++) for(int j=0; j<n; j++) { memset(b,0,sizeof(b)); for(int k=0;k<n;k++) for(int m=i;m<=j;m++) b[k]+=a[m][k]; int maxs=b[0]; for(int k=1;k<n;k++) { if(b[k-1]>0) b[k]+=b[k-1]; maxs=max(maxs,b[k]); } ans=max(maxs,ans); } printf("%d\n",ans); return 0;}
POJ 1050 To the Max 枚举+dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。