HDU 1559 最大子矩阵

举报
Linux猿 发表于 2021/08/06 00:00:06 2021/08/06
【摘要】 题目链接~~> 做题感悟:这题一看就想出一种方法,虽然有点慢,但是还凑合! 解题思路:一、用 dp [ i ][ j ] 记录dp[ i ] [ 0 ] 到 dp [ i ] [ j ]的和计算的时候依次加起来,利用了前缀和的思想。二、用dp[ i ][ j ] 记录 dp [ 0 ][ 0 ] 到dp[ i ] [ j ] 这个矩形的...

题目链接~~>

做题感悟:这题一看就想出一种方法,虽然有点慢,但是还凑合!

解题思路:一、用 dp [ i ][ j ] 记录dp[ i ] [ 0 ] 到 dp [ i ] [ j ]的和计算的时候依次加起来,利用了前缀和的思想。二、用dp[ i ][ j ] 记录 dp [ 0 ][ 0 ] 到dp[ i ] [ j ] 这个矩形的面积。

代码(方法一): 


      #include<stdio.h>
      #include<iostream>
      #include<map>
      #include<string>
      #include<string.h>
      #include<stdlib.h>
      #include<math.h>
      #include<vector>
      #include<queue>
      #include<algorithm>
      using namespace std ;
      #define pret(a,b) memset(a,b,sizeof(a))
      const int  INF = 99999999 ;
      const double esp = 0.000000001 ;
      const int MX = 1005 ;
      int n,m,x,y ;
      int dp[MX][MX],best ;
      void DP()
      {
       best=0 ;
      for(int j=1 ;j<=m-y+1 ;j++) // 列
      for(int i=1 ;i<=n-x+1 ;i++)  // 行
       {
      int mx=0 ;
      for(int k=i ;k<=i+x-1 ;k++)
       mx+=dp[k][j+y-1]-dp[k][j-1] ;
       best= best > mx ? best : mx ;
       }
      }
      int main()
      {
      int T ;
      scanf("%d",&T) ;
      while(T--)
       {
      scanf("%d%d%d%d",&n,&m,&x,&y) ;
      memset(dp,0,sizeof(dp)) ;
      for(int i=1 ;i<=n ;i++)
      for(int j=1 ;j<=m ;j++)
       {
      scanf("%d",&dp[i][j]) ;
       dp[i][j]+=dp[i][j-1] ;
       }
       DP() ;
      printf("%d\n",best) ;
       }
      return 0 ;
      }
  
 

代码(方法二):


      #include<iostream>
      using namespace std;
      #define N 1001
      int dp[N][N];
      int main(void)
      {
     	int t;
     	int n,m,x,y;
     	scanf("%d",&t);
     	while(t--)
      	{
     		scanf("%d%d",&n,&m);
     		scanf("%d%d",&x,&y);
     		memset(dp,0,sizeof(int)*n*m);
     		int M=INT_MIN;
     		for(int i=1;i<=n;i++)
     			for(int j=1;j<=m;j++)
      			{
      scanf("%d",&dp[i][j]);
       dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
      if(i>=x&&j>=y)
       {
      int temp=dp[i][j]-dp[i-x][j]-dp[i][j-y]+dp[i-x][j-y];
      if(temp>M)
       M=temp;
       }
      			}
     		printf("%d/n",M);
      	}
      }
  
 


 

 

文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/nyist_zxp/article/details/21218663

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。