最大子阵

今天药忘吃喽~ 2024-02-17 18:43 66阅读 0赞

### Description ###

### 给定一个n\*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。其中，A的子矩阵指在A中行和列均连续的一块。 ###

### Input ###

输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。  
接下来n行，每行m个整数，表示矩阵A。

（1 <= n, m <= 50，1 <= n, m <= 500，A中每个元素的绝对值不超过5000）

### Output ###

输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。

### Sample Input ###

3 3

-1 -4 3

3 4 -1

-5 -2 8

### Sample Output ###

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> 
    <div>
      15 
    </div> 
    <div>
      16 
    </div> 
    <div>
      17 
    </div> 
    <div>
      18 
    </div> 
    <div>
      19 
    </div> 
    <div>
      20 
    </div> 
    <div>
      21 
    </div> 
    <div>
      22 
    </div> 
    <div>
      23 
    </div> 
    <div>
      24 
    </div> 
    <div>
      25 
    </div> 
    <div>
      26 
    </div> 
    <div>
      27 
    </div> 
    <div>
      28 
    </div> 
    <div>
      29 
    </div> 
    <div>
      30 
    </div> 
    <div>
      31 
    </div> 
    <div>
      32 
    </div> 
    <div>
      33 
    </div> 
    <div>
      34 
    </div> 
    <div>
      35 
    </div> 
    <div>
      36 
    </div> 
    <div>
      37 
    </div> 
    <div> 
     <br> 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>#include&lt;cstdio&gt;</code> 
     </div> 
     <div> 
      <code>#include&lt;string.h&gt;&nbsp;</code> 
     </div> 
     <div> 
      <code>int</code> 
      <code> A[505][505]; </code> 
     </div> 
     <div> 
      <code>int</code> 
      <code> dp[505];&nbsp; </code> 
     </div> 
     <div> 
      <code>int</code> 
      <code> Onemax(</code> 
      <code>int</code> 
      <code>dp[],</code> 
      <code>int</code> 
      <code>m){ &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;//此处为最大子序列求解</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>max=dp[0],temp=0; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>i=0;i&lt;m;i++){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>temp+=dp[i];</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(max&lt;temp){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>max=temp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(temp&lt;0)temp=0;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>max; </code> 
     </div> 
     <div> 
      <code>} </code> 
     </div> 
     <div> 
      <code>int</code> 
      <code> main(){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>n,m; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(</code> 
      <code>scanf</code> 
      <code>(</code> 
      <code>"%d%d"</code> 
      <code>,&amp;n,&amp;m)==2){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>i=0;i&lt;n;i++){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>j=0;j&lt;m;j++){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>scanf</code> 
      <code>(</code> 
      <code>"%d"</code> 
      <code>,&amp;A[i][j]);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>max1=A[0][0]; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>i=0;i&lt;n;i++){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>memset</code> 
      <code>(dp,0,</code> 
      <code>sizeof</code> 
      <code>(dp));</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>j=i;j&lt;n;j++){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>k=0;k&lt;m;k++){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>dp[k]+=A[j][k];</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}&nbsp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>temp=Onemax(dp,m); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(temp&gt;max1)max1=temp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}&nbsp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>printf</code> 
      <code>(</code> 
      <code>"%d\n"</code> 
      <code>,max1);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>0; </code> 
     </div> 
     <div> 
      <code>} </code> 
     </div> 
     <div> 
      <br> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>