hdu 1559 최대 서브 매트릭스

최대 서브 매트릭스
Time Limit: 30000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2138 Accepted Submission(s): 1077
Problem Description
m 줄 게.×n 의 정수 행렬, 위 에서 x 를 찾 습 니 다.×y 의 서브 매트릭스, 서브 매트릭스 의 모든 요소 와 최대.

Input
데 이 터 를 입력 하 는 첫 번 째 행 위 는 T 조 테스트 데이터 가 있 음 을 나타 내 는 정수 T 입 니 다.각 조 테스트 데이터 의 첫 번 째 행 위 는 네 개의 정수 m, n, x, y (0) 이다.

Output
각 그룹의 데이터 에 대해 하나의 정 수 를 출력 하면 서브 매트릭스 의 최대 합 을 나타 낸다.

Sample Input

 
   
     1 4 5 2 2 3 361 649 676 588 992 762 156 993 169 662 34 638 89 543 525 165 254 809 280

Sample Output

Author

lwg

Source

HDU 2006-12 Programming Contest

Recommend

一般的朴素算法都会超时。要采用记忆式算法。减少求和次数以提高效率。

#include 
#include

int num[1010][1010];//num   (0,0)(i,j)      
int main()
{
    int t,m,n,x,y,i,j,temp,ans;

    scanf("%d",&t);
    while(t--)
    {
        memset(num,0,sizeof num);
        scanf("%d%d",&m,&n);
        scanf("%d%d",&x,&y);
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=n;j++)
            {
                scanf("%d",&temp);//       
                num[i][j]=num[i-1][j]+num[i][j-1]-num[i-1][j-1]+temp;
            }
        }
        ans=0;
        for(i=x;i<=m;i++)//          。
        {
            for(j=y;j<=n;j++)
            {
                temp=num[i][j]-num[i-x][j]-num[i][j-y]+num[i-x][j-y];//      
                if(ans

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

hdu 1559 최대 서브 매트릭스

최대 서브 매트릭스 Time Limit: 30000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 21...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

hdu 1559 최대 서브 매트릭스

좋은 웹페이지 즐겨찾기