题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1081
解题报告:求最大的矩阵和的问题,可以转化为最大连续子序列和的模型,只不过这个是一个二维的问题。如何转化是关键:我们可以把每一项变成前面多项的和,通过相减计算每个子矩阵。在求解的时候竖着求解,这样子问题就转换为1维求解最大连续子序列和的问题。
给一组参考数据:
4
-3 -7 -1 -2
-3 -4 -2 -5
-3 -5 -2 -3
-4 6 -3 -2
参考代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAX (100 + 5) int mp[MAX][MAX],sum[MAX][MAX]; int temp[MAX][MAX]; int main() { int n,ans,cnt; while(scanf("%d",&n)!=EOF) { int mini = -0x7ffffff; memset(mp,0,sizeof(mp)); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&mp[i][j]); if(mp[i][j] > mini) mini = mp[i][j]; } if(mini<0) { printf("%d\n",mini); continue; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) sum[i][j]=sum[i][j-1]+mp[i][j]; } ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { for(int k=0;k<i;k++) { temp[j][k+1]=sum[j][i]-sum[j][k]; } } for(int k=1;k<=i;k++) { cnt=0; for(int j=1;j<=n;j++) { cnt+=temp[j][k]; if(ans<cnt) ans=cnt; if(cnt<0) cnt=0; } } } printf("%d\n",ans); } return 0; }
相关推荐
关于hdu的动态规划的题目,包括一些水题,还有一些经典的动态规划题目。
动态规划DP题解 POJ HDU部分动态规划DP题解
HDU 动态规划(46道题目
hdu动态规划算法集锦
HDU的一题........HDU DP动态规
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
杭电ACM课件2014版之 (HDUACM201403版_05)动态规划
HDU动态规划,此PPT系杭州电子科技大学ACM总教练刘春英老师所有, 特在此分享贡献给广大编程爱好者, 特别是ACMer!
动态规划DP题解 POJ HDU 动态规划解题报告
算法设计与分析实验六:使用动态规划算法解决存钱问题(java实现、hdu1114)(csdn)————程序
(lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_7)特殊的数 (lecture_8)组合博弈入门 (lecture_09贪心算法 (lecture_11)搜索入门 (lecture_12)二分匹配及其应用 ...
杭电ACMhdu1163
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu1001解题报告
HDU1059的代码
hdu 1574 passed sorce
hdu2101AC代码
动态规划入门,hdu上的动态规划入门题的结题报告。 hdu 1171,hdu 1059,hdu 2159,hdu 2191,hdu 3496
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241