[既知のポイント]フェンスのトリム

質問する

同じ幅のN枚の板で綴った柵があります.時間が経つにつれて、板が折れたり壊れたりして高さが違うので、柵全体を交換することにしました.このとき、捨てた柵の一部を矩形に切ってから利用したいと思います.図(b)は、(a)のグリッドから切り取ることができる多くの矩形の中で最も広い矩形を示す.フェンスを構成する各プレートの高さを指定する場合は、切り取り可能な矩形の最大寸法を計算するプログラムを作成します.(c)のように矩形を斜めに切ることはできません.
プレートの幅はいずれも1であると仮定します.

入力

1行目のテストケース数C(C≦50).各テストケースの最初の行には、ボード数N(1≦N≦20000)が含まれる.次の行はN個の整数で、各プレートの高さを左から右に順に与えます.高さはすべて整数ですが、10000以上です.

しゅつりょく

各テストケースは、1行に整数を出力します.この整数は、指定されたグリッドから切り取ることができる最大長方形のサイズを表す必要があります.

入力例

3
7
7 1 5 9 6 7 3
7
1 4 4 4 4 1 1
4
1 8 2 2

サンプル出力

20
16
8

Concept

初めて接触したとき、これは非常に理解しにくい問題に見えました.繰り返しのbrute forceだけを使うと必ずタイムアウトするので、ある程度の回帰で実現しようとします.
教材のアイデアを参考にして、私が書いたコードは以下の通りです.

#include <iostream>
#include <vector>
using namespace std;
int arr[20001];

int fence(int start, int end){ // 0 6
    if (start==end) return arr[start];
    if (start+1==end) return 2*min(arr[start], arr[end]);
    int mid = (start+end)/2;
    
    //case 1 : 기준(mid)의 왼쪽에서만 답이 생길 경우
    int Square1=fence(start, mid-1);
    
    //case 2 : 기준의 오른쪽에서만 답이 생길 경우
    int Square2=fence(mid+1, end);
    
    //case 3 : 기준이 포함되어 답이 생길 경우
    int Square3=-1, rect;
    for (int i=start; i<=mid; i++){ // i는 직사각형의 가장 왼쪽
        for (int j=mid; j<=end; j++){ // j는 직사각형의 가장 오른쪽
            int minHeight=10001;
            for (int k=i; k<=j; k++){ //k는 i~j까지의 가장 낮은 높이를 구하기 위함
                if (arr[k] < minHeight) minHeight = arr[k];
            }
            rect = minHeight*(j-i+1);
            if (Square3<rect) Square3 = rect;
        }
    }
    
    return (Square1>Square2) ? ((Square1>Square3)? Square1 : Square3) : ((Square2>Square3)? Square2 : Square3);
}

int main(){
    int c;
    cin>>c;
    for (int h=0; h<c; h++){ // case별
        int n;
        cin>>n;
        for (int i=0; i<n; i++){
            cin>>arr[i];
        }
        // 0 1 2 3 4 5 6
        // 7 1 5 9 6 7 3
        cout<<fence(0, n-1)<<endl;
    }
}

例は正常に動作していますが、結果はタイムアウトしました.
本当に知らなかったので、ネットで検索してみると、上のfor文が2つ使われていました.
midの左と右をそれぞれのインデックスで線形に決定すると,時間複雑度O(n)で解決できる問題は,2つのゲート,時間複雑度O(n^2)を用いなければならない.
インターネット上のコードを参照すると、次のように記述できます.

Code

#include <iostream>
#include <vector>
using namespace std;
int arr[20001];

int fence(int start, int end){ // 0 6
    if (start==end) return arr[start];
    if (start+1==end) return 2*min(arr[start], arr[end]);
    int mid = (start+end)/2;
    
    //case 1 & 2 : 기준(mid)의 왼쪽, 오른쪽에서만 답이 생길 경우
    int Square1=max(fence(start, mid-1), fence(mid+1, end));
    
    
    //case 3 : 기준이 포함되어 답이 생길 경우
    int height = arr[mid];
    int width = 1;
    int Square2= max(Square1, height*width);

    int l = mid-1;
    int r = mid+1;
    
    //선형적으로 탐색한다. (O(n))
    while(start<=l || r <=end){
        if (start > l || (arr[l] <= arr[r] && r <= end)){ // right이 더크면
            height = min(height, arr[r]); // 오른쪽으로 넓힌다.
            r++; //그다음 index update
            width++;
            Square2 = max(Square2, width*height);
        }
        else if (r > end || (arr[l]>= arr[r] && start<=l)){ // left가 더 크면
            height = min(height, arr[l]); // 왼쪽으로 넓힌다.
            l--;
            width++;
            Square2 = max(Square2, width*height);
        }
        else break;     //왼쪽 index와 오른쪽 index가 둘 다 범위를 벗어나면 종료.
    }
    return Square2;
    
    
    
}

int main(){
    int c;
    cin>>c;
    for (int h=0; h<c; h++){ // case별
        int n;
        cin>>n;
        for (int i=0; i<n; i++){
            cin>>arr[i];
        }
        // 0 1 2 3 4 5 6
        // 7 1 5 9 6 7 3
        cout<<fence(0, n-1)<<endl;
    }
}

Comment

そのようにwhileゲートを用いてインデックスを線形に拡張する問題はよくない.
配列の大きさに常に注意し,線形法を熟知しなければならない.
でもこの和弦は間違っていますここを見て...