2019 뉴커머스 여름방학 다교훈련캠프(제2차) H:Second Large Rectangle(dp or 단조창고)

제목: 0과 1을 포함하는 행렬을 지정합니다. 출력 사각형 안에 1의 두 번째 큰 사각형의 크기가 있습니다.

분석: 고전 문제의 변형에서 온 상세한 설명https://www.cnblogs.com/linkstar/p/6139668.html, dp와 단조로운 창고 두 가지 해법은 코드를 향해 한 번 뛰는 것이 더 이해가 된다.dp가 더 잘 이해되고 복잡도가 약간 높다.두 번째 큰 것이 반드시 가장 큰 방법을 구하는 두 번째 큰 것이 아니라, 한 줄이나 한 열의 크기를 가장 크게 줄일 수도 있으니 주의해라.

dp 코드:

#include
using namespace std;
const int N = 1e3+5;
int dp[N][N];
int n,m,sum=-1,ans=-1;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%1d",&dp[i][j]);
            dp[i][j]+=dp[i-1][j]*dp[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int len=dp[i][j],dep=1;
            while(len)
            {
                int area=len*dep;
                if(area>ans)
                {
                    sum=ans;ans=area;
                }
                else if(area>sum)
                {
                    sum=area;
                }
                len=min(len,dp[i][j-dep]);
                dep++;
            }
        }
    }
    if(sum==-1) sum=0;
    printf("%d
",sum);
    return 0;
}

스택 코드:

#include
using namespace std;
const int N = 1e3+5;
int dp[N][N];
int n,m,sum=-1,ans=-1;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%1d",&dp[i][j]);
            dp[i][j]+=dp[i-1][j]*dp[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int len=dp[i][j],dep=1;
            while(len)
            {
                int area=len*dep;
                if(area>ans)
                {
                    sum=ans;ans=area;
                }
                else if(area>sum)
                {
                    sum=area;
                }
                len=min(len,dp[i][j-dep]);
                dep++;
            }
        }
    }
    if(sum==-1) sum=0;
    printf("%d
",sum);
    return 0;
}