https://zerojudge.tw/ShowProblem?problemid=o076
題意#
有一個城鎮有 \(n\) 棟高樓，樓高分別為 \(h_1, h_2, \dots, h_n\)。市長想要在城鎮中心舉辦高空特技表演，該特技表演會從某棟大樓上朝右側滑翔至地面。
想法#
首先，題目說「滑翔的路徑樓高必須越來越低」，轉換成更具體一點的概念就是要找到一對 \(l\)、\(r\) 滿足 \(h_l > h_{l+1}>\dots >h_{l+2}>h_r\)，並且 \(r-l+1\) 要盡可能的大。
接下來，我們只要透過檢查每一對 \(l、r\) 判斷是否合法，並記錄最大的答案就行了！
#include <bits/stdc++.h>
using namespace std;
// 大樓高度
int h[100];
// 判斷大樓 l 到大樓 r 是否可以滑翔 (是否嚴格遞減)
bool ok(int l, int r) {
for (int i = l; i <= r-1; i++) {
if (h[i + 1] >= h[i]) return false;
}
return true;
}
int main() {
int n;
cin >> n;
int ans = 0;
for (int i = 1; i <= n; i++) cin >> h[i];
// 嘗試每一對 l r
for (int l = 1; l <= n; l++) {
for (int r = l + 1; r <= n; r++) {
// 檢查是否合法，如果合法就嘗試更新答案
if (ok(l, r)) ans = max(ans, r - l + 1);
}
}
// 輸出答案
cout << ans << endl;
}
