최대 서브 행렬은 전형적인 dp 문제다.어느 정도는 최대 연속 서열과 문제의 확장이라고 할 수 있다.

1081

원제 주소

이것은 가장 흔히 볼 수 있는 최대 하위 행렬 문제의 체형이다.간단한 해결 방안은 열을 누적하여 임의의 두 줄의 누적값의 차이를 두루 훑어본 다음에 일반적인 최대 연속 서열과 문제로 전환하는 것이다.따라서 2차원 문제를 1차원으로 전환한다.시간 복잡성이 높은 O(N^3)

코드:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX=104;
int a[MAX][MAX];
int dp[MAX];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof a);
        memset(dp,0,sizeof dp);
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                scanf("%d",&a[i][j]);
                a[i][j]+=a[i-1][j];
            }
        }
        int max_sum=0;
        for(int i=1; i<=n; i++)
        {
            for(int j=0; j<i; j++)
            {
                for(int k=1; k<=n; k++)
                {
                    dp[k]=a[i][k]-a[j][k];
                    dp[k]+=dp[k-1];
                    if(dp[k]<0)
                        dp[k]=0;
                    if(dp[k]>max_sum)
                        max_sum=dp[k];
                }
            }
        }
        printf("%d
",max_sum);
    }
}

매트릭스 값을 입력할 때 처리를 했는데,
a[i][j]+=a[i-1][j]로 인해 a매트릭스에서 a[i][k]는 원 매트릭스에서 k열 원소를 저장하고 위에서 i열 원소의 합을 누적한다.
그래서 아래의 dp[k]=a[i][k]-a[j][k], dp[k]는 원 행렬의 k열에서 i행에서 j행까지의 원소와
3층 for 순환, 앞의 2층 순환은 임의의 두 줄을 반복하는 차이값이다.즉 서브 행렬의 첫 줄과 끝 줄의 모든 상황을 두루 훑어보는 것이다.
내부 3층 for순환은 일반적인 구해 1차원 최대 연속자 서열과 구법이다.

1559

원제 주소

이 문제는 이전 문제와 달리 두 가지 제한 조건을 추가했다. 바로 서브 행렬의 두 차원은 반드시 주어진 x, y값이어야 한다는 것이다.
4

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX=1004;
int a[MAX][MAX];
int dp[MAX];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int m,n,x,y;
        memset(a,0,sizeof a);
        scanf("%d%d%d%d",&m,&n,&x,&y);
        for(int i=1; i<=m; i++)
        {
            for(int j=1; j<=n; j++)
            {
                scanf("%d",&a[i][j]);
                a[i][j]+=a[i-1][j];
            }
        }
        int max_sum=0;
        for(int i=x; i<=m; i++)
        {
            for(int j=1; j<=n; j++)
            {
                dp[j]=a[i][j]-a[i-x][j];
                dp[j]+=dp[j-1];
                if(j>=y)
                {
                    max_sum=max(max_sum,dp[j]-dp[j-y]);
                }
            }
        }
        printf("%d
",max_sum);
    }
}

대동소이, 관건은
결정을 내릴 때.pp[j]-dp[j-y]는 원 행렬에서 (i, j)를 오른쪽 하각 원소로 하고 행수는 x이며 열수는 y의 하위 행렬과를 나타낸다.