首页 > 代码库 > POJ1050：To the max
POJ1050：To the max
poj1050：http://poj.org/problem?id=1050
* maximum-subarray 问题的升级版本~
本题同样是采用DP思想来做，同时有个小技巧处理：就是把二维数组看做一维数组。怎么去看呢，我们可以吧具有同样列号的数捆绑到一起，比如 a[1][1], a[2][1], a[3][1]....。我们可以吧他们都看做 ‘a[1]‘。因为最终的解是矩阵行数n中的任意一段，比如说：第p行到第q行, (1<=p<=q<=n), 我们要得到最终解，就一定要逐一枚举p，q。
* 如果p==q的话，就说明当前考察的矩阵只有一行，所以问题就很简单啦，在这一行上利用maximum-subarray DP解法就可以得到子矩阵a[p或者q][1...n]的最大和S1。
* 如果p！=q时，说明考察的巨狠是多行的，为了把多行变成‘一行‘，我们可以吧从p行到q行的矩阵同一列的值相加，比如:
第p行: a[p][1], a[p][2], .... , a[p][n]
第p+1行：a[p+1][1], a[p+1][2], ... , a[p+1][n]
..........
第q行： a[q][1], a[q][2], ... , a[q][n]
相加---!> a[p][1]+...+a[q][1] , ... , a[p][n]+...+a[q][n]
这样我们在这个新的一维矩阵上又可以进行maximum-subarray DP解法，得到最大和S2。
并且每一次枚举p，q时得到的S1或者S2，我们都要和最终结果ans进行比较，将其中较大的值存入ans中。
细节看代码：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 using namespace std; 6 const int max_size=101; 7 const int inf=(1<<30); 8 int a[max_size][max_size]; 9 int n;10 int main(){11 scanf("%d",&n);12 memset(a,0,sizeof(a));13 for(int i=1;i<=n;i++){14 for(int j=1;j<=n;j++){15 scanf("%d",&a[i][j]);16 if(i>=2) a[i][j]+=a[i-1][j];17 } 18 }19 //int *tmp=new int[(n+1)*n][m+1];20 int ans=-inf,sum;21 for(int i=1;i<=n;i++){22 //memset(tmp,0,sizeof(tmp));23 for(int j=i;j<=n;j++){24 if(j==i) sum=a[i][1];25 else sum=a[j][1]-a[i-1][1];26 for(int k=2;k<=n;k++){27 if(j==i){28 if(sum>0){29 sum+=a[i][k];30 } 31 else{32 sum=a[i][k];33 } 34 if(sum>ans) ans=sum;35 }36 else{37 if(sum>0){38 sum+=a[j][k]-a[i-1][k];39 } 40 else{41 sum=a[j][k]-a[i-1][k];42 } 43 if(sum>ans) ans=sum;44 }45 }46 }47 }//end for48 printf("%d\n",ans); 49 }
POJ1050：To the max
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。