了解点:垣根をトリムする

リンク:https://algospot.com/judge/problem/read/FENCE

問題を読む

無知に解決しよう。

排板高さでh[]に処理し、l号板からr号板まで矩形に切り取る(l∧r+1)×mini=lrh[i](l-r+1)\times{min_{i=l}^{r}}h[i](l−r+1)×mini=lrh[i]式.

分割征服アルゴリズムの設計

n枚の板を半分に分けて、2つの部分に変える問題.我々が見つけた最大矩形は以下の3つのいずれかに属する.

最大の長方形は左側の問題でしか見つからない.

最大の矩形は右側の問題でしか見つからない.

最大の長方形は、左側と右側にまたがっています.

双方とも問題がある。

答え矩形が局所問題境界上の2つの板を含まなければならないことを考慮して,それを探した.

コード#コード#

#include<iostream>
#include<vector>
using namespace std;

vector<int> h;

int solve(int left, int right) {
	if (left == right) return h[left];
	int mid = (left + right) / 2;
	int ret = max(solve(left, mid), solve(mid + 1, right));
	int lo = mid, hi = mid + 1;

	int height = min(h[lo], h[hi]);

	ret = max(ret, height * 2);
	while (left < lo || hi < right) {
		if (hi < right && (lo == left || h[lo - 1] < h[hi + 1])) {
			++hi;
			height = min(height, h[hi]);
		}
		else {
			--lo;
			height = min(height, h[lo]);
		}
		ret = max(ret, height * (hi - lo + 1));
	}
	return ret;

}

int main() {
	int C, N, elem;
	cin >> C;
	for (int i = 0; i < C; i++) {
		cin >> N;
		for (int j = 0; j < N; j++) {
			cin >> elem;
			h.push_back(elem);
		}
		cout << solve(0, N-1) << endl;
		h.clear();
	}
	return 0;
}

ぶんせき

nサイズのアレイを2つのn 2frac{n}22 nサイズのアレイに分割した後,それぞれ解決する過程である.再帰呼び出し関数に加えて,関数内で行われる作業は2つの部分の矩形を探すことであり,この作業の時間的複雑さは時間全体の複雑さを決定する.分割征服アルゴリズムは,合成秩序と同じ時間複雑度O(nlgn)O(nlgn)O(nlgn)O(nlgn)を持つ.

int height = min(h[lo], h[hi]);
ret = max(ret, height * 2);

この部分を見てみましょう.2つの部分がまたがる矩形の中で最大の1つを探す過程を経なければなりません.左または右の最小値を見つけ、retと比較して2を乗算します.どうしてですか.
これは[mid,mid+1]のみを含む幅が2の矩形を考えるためである.retは矩形の幅の変数を指す.したがって、計算は、私たちが探している境界線を含む矩形を基準とするのではなく、左または右に1つだけ隔てた矩形を考慮します.
しかしコメントでは2のforゲートで解決するのがもっと速いと言っています再帰関数のための問題と見なしましょう.