Ural 1146 Maximum Sum（DP）-白红宇

Ural 1146 Maximum Sum（DP）

阅读量：4511 次

发布时间：2019-06-08

本文共 795 字，大约阅读时间需要 2 分钟。

题目地址：

这题是求最大子矩阵和。方法是将二维转化一维。

首先用n*n的方法来确定矩阵的列。须要先进行预处理，仅仅对每行来说，转化成一维的前缀和，这样对列的确定仅仅须要前后两个指针来确定。仅仅须要用前缀和相减就可以得到。前后两个指针用n*n的枚举。

确定好了哪几列，那么再确定行的时候就转化成了一维的最大连续子序列的和。

再来一次O(n)的枚举就能够。

这样，总复杂就变成了O(n^3)。对于n为100来说，已经足够了。

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;const int INF=0x3f3f3f3f;#define LL long longint dp[200][200];int main(){ int n, i, j, k, sum, x, max1; while(scanf("%d",&n)!=EOF) { max1=-INF; memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&x); dp[i][j]=dp[i][j-1]+x; } } for(i=1;i<=n;i++) { for(j=0;j

转载于:https://www.cnblogs.com/gcczhongduan/p/5261310.html

你可能感兴趣的文章