HDU 1559 最大子矩阵
【摘要】 题目链接~~>
做题感悟:这题一看就想出一种方法,虽然有点慢,但是还凑合!
解题思路:一、用 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)