題目 3334: 藍橋杯2025年第十六屆省賽真題-園藝
時間限制: 2s 內存限制: 192MB 提交: 129 解決: 37
題目描述
小藍從左到右種了 n 棵小樹，第 i 棵樹的高度為 hi ，相鄰樹的間隔相同。 小藍想挪走一些樹使得剩下的樹等間隔分布，且從左到右高度逐漸上升（相鄰 兩棵樹高度滿足右邊的比左邊的高），小藍想知道最多能留下多少棵樹。

輸入格式
輸入的第一行包含一個正整數 n 。?

第二行包含 n 個正整數 h1, h2, · · · , hn ，相鄰整數之間使用一個空格分隔。

輸出格式
輸出一行包含一個整數表示答案。

樣例輸入復制
6
3 5 4 7 6 7
樣例輸出復制
3
提示
【樣例說明】?

留下第 1、3、5 棵樹，它們等間隔且從左到右高度逐漸上升。?

【評測用例規模與約定】?

對于 30% 的評測用例，1 ≤ n ≤ 500 ；?

對于 60% 的評測用例，1 ≤ n ≤ 3000 ；

對于所有評測用例，1 ≤ n ≤ 5000 ，0 < hi < 106 。

1.分析

? ? ? ? 遍歷所有開始下標和間隔。

? ? ? ? 注意要實時更新數量，可能不連續。

2.代碼

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int MAX = 1e4 + 10;
typedef long long LL;
int n,a[MAX],re;
int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}for (int i = 0; i < n; i++) {for (int k = 0; k <= i; k++) {int num = 0, t = -1;for (int j = k; j < n; j += i + 1) {if (a[j] > t) {t = a[j];num++;re = max(re, num);}else {num = 1;t = a[j];} }}}cout << re << endl;return 0;
}