사실 작년 9월에 이 두 문제를 했었어요.

hdu1506Largest Rectangle in a Histogram

hdu1505city game dp

그러나 단조로운 창고로 최적화된 것이 아니라 이해하기 어려운 방법으로 한 것이다. 다시 한 번 쓰라고 하면 멍한 얼굴일 것이다. QAQ는 어제 저녁까지 작은 섬의 생방송을 봤다.
비록 말은 정말 너무 빠르지만, 단조로운 창고라는 물건은 정말 잘 배워야 할 것 같다.
먼저 첫 번째 문제를 통해 단조 창고의 유지 보수를 설명한다.
예시수조: 7,2,1,4,5,1,2,3 최대 서브 행렬의 면적은 8
전체 그룹을 훑어볼 때 현재 숫자보다 작은 값을 저장하는 점증 창고를 유지합니다.왜?기왕 포위된 바에는 반드시 직사각형의 좌우변이 가장 짧고 두 번째로 짧은 것이 틀림없다. 우리는 비교적 짧은 두 개의 포위된 직사각형(이 두 개의 짧은 변 사이의 변이 모두 이 두 개보다 짧지 않다)을 찾아서 포위된 면적을 확정할 수 있다.만약에 오른쪽의 변이 가장 작은 변이라면 이 변은 오른쪽 경계와 왼쪽이 이 변보다 작은 변의 중간에 있는 모든 긴 변으로 직사각형을 둘러싸고 중간의 이 변들을 우리가 두루 돌아다닐 수 있다. 두루 돌아다닐 때 점증 창고 보존 숫자를 유지할 수 있고 구체적인 수조 유지 보수 과정은 다음과 같다.
먼저 0 입고(수 그룹 아래 표시는 1부터)를 표시하고 맨 왼쪽 0 위치의 수치 0을 입고한다.모든 숫자를 두루 훑어보았을 때 창고 꼭대기 요소가 현재 요소보다 크고 출고하는 것을 발견하면 최대 면적(면적의 높이는 창고 꼭대기 요소, 너비는 창고 꼭대기 원소의 거리 -1, -1은 창고 꼭대기 원소가 비교적 작은 값이기 때문)을 계산하고 갱신한다. 이 동작을 창고 꼭대기 원소가 이 원소의 값보다 작을 때까지 지속한다.매번 숫자를 옮겨다니며 그것을 창고에 넣는다

#include 
#include
#include
using namespace std;
const int N=int(1e5)+9;
int h[N];
int n;
int main()
{
    while(cin>>n&&n)
    {
        for(int i=1;i<=n;i++)scanf("%d",&h[i]);
        long long ans=0;
        stacks;s.push(0);h[++n]=0;
        for(int i=1;i<=n;i++)
        {
            while(h[i]ans)ans=a*b;
            }
            s.push(i);
        }
        printf("%lld
",ans);
    }
    return 0;
}

다음 문제는 2차원에서 최대 면적을 찾아내는 것으로 바꿨다.이러한 모델을 추상화해 낸다. 조건을 만족시키는 직사각형을 찾으면 그 아래 경계는 이전 문제의 밑바닥으로 볼 수 있다.이렇게 생각하면 하기 쉽다. 한 줄 한 줄 열거하면 위에서 지난 문제의 도형을 처리할 수 있다. 없어졌다.

#include 
#include
#include
#include
using namespace std;
int h[1009],n,m,t;
char str[1009];
int main()
{
  //  freopen("cin.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(h,0,sizeof(h));
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%s",str);
                if(i!=1)
                {
                    if(str[0]=='F')h[j]=h[j]+1;
                    else h[j]=0;
                }
                else
                {
                    if(str[0]=='F')h[j]=1;
                    else h[j]=0;
                }
            }
           // for(int j=1;j<=m;j++)printf("i=%d,j=%d,h=%d
",i,j,h[j]);
            stacks;s.push(0);h[m+1]=0;
            for(int j=1;j<=m+1;j++)
            {
                while(h[j]ans)ans=a*b;
                }
                s.push(j);
            }
        }
        printf("%d
",ans*3);
    }
    return 0;
}