35 · 模拟赛一：120 分钟 4 题

设留下的人里最高的那位站在位置 i。那么：

· i 左边的人必须构成以 i 结尾的严格递增序列，最多能留 up[i] 人（含 i 自己）；

· i 右边的人必须构成从 i 开始的严格递减序列；把数组倒过来看，就是以 i 结尾的严格递增序列，最多能留 down[i] 人（含 i 自己）。

两段共享 i 这个点，所以以 i 为峰能留下 up[i] + down[i] − 1 人。枚举所有 i 取最大值 best，答案就是 n − best。

up 的求法就是 LIS 的 O(n²) 写法：up[i] = 1 + max{ up[j] : j < i 且 a[j] < a[i] }。down 可以用同一段代码算两次：先把数组反转，跑一遍 up，再反转回来。

为什么“只看 i 左边”就够：因为左右两侧的人选互相独立——左边的人只受左半边约束，右边只受右半边约束，唯一的交集是峰 i 本身，所以直接相加再减 1。

复杂度 O(n²)。n ≤ 100 时只有 10⁴ 次比较，随便过。

注意“严格”二字：身高相同的两人不能同时出现在递增段里，所以比较必须写 a[j] < a[i]，不能写 <=。

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int n, a[N], up[N], down[N];

// 求以每个位置结尾的最长严格上升子序列长度，存进 f[]
void lis(int f[]) {
    for (int i = 1; i <= n; ++i) {
        f[i] = 1;                          // 至少能只留自己
        for (int j = 1; j < i; ++j)
            if (a[j] < a[i])               // 严格递增：不能取等
                f[i] = max(f[i], f[j] + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    lis(up);                               // 从左往右：以 i 结尾的最长递增

    reverse(a + 1, a + n + 1);             // 倒过来
    lis(down);                             // 现在还叫 down，含义是"以 i 开头的递减"
    reverse(down + 1, down + n + 1);       // 把 down 的下标对回去，与原来的 i 对齐
    reverse(a + 1, a + n + 1);             // a 恢复原样（其实后面不用了，但别留坑）

    int best = 0;
    for (int i = 1; i <= n; ++i)
        best = max(best, up[i] + down[i] - 1);   // 峰 i 被两边都算了一次，减 1

    cout << n - best << "\n";              // 问的是出列人数
    return 0;
}

条件具有单调性：区间变长只会更容易覆盖全部 M 种，变短只会更难。这就是双指针的入场券。

维护窗口 [l, r]、计数数组 cnt[画家] 和 have = 窗口内出现的不同画家数。

r 从 1 扫到 N，每步把 a[r] 加入窗口；只要 have == M，就尝试收缩 l：先用当前长度更新答案，再把 a[l] 移出、l 右移。

正确性：对固定的 r，while 循环退出时 [l, r] 是“以 r 结尾的最短合法窗口”。任何以 r 结尾的合法窗口都包含它、更长，所以不可能更优——只检查这一个就够，不漏解。

字典序 tie-break：长度相同取 a 最小。r 是从小到大扫的，而长度相同的两个区间，右端点更小的那个左端点也更小；配合“只在严格更短时更新答案”，第一个被记下的最短解就是 a 最小的。

复杂度 O(N)：l、r 各走不超过 N 步。N = 10⁶ 时约 2×10⁶ 次操作，稳过。

#include <bits/stdc++.h>
using namespace std;

int a[1000005];        // N ≤ 10⁶，上限 +5，少开就是 RE
int cnt[2005];         // M ≤ 2000：cnt[x] = 窗口内画家 x 的画有几幅

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    int l = 1, have = 0;                       // have：窗口内不同画家的种数
    int bestLen = INT_MAX, bestL = 0, bestR = 0;

    for (int r = 1; r <= n; ++r) {
        if (++cnt[a[r]] == 1) ++have;          // 加进来后计数为 1：这是新画家
        while (have == m) {                    // 已覆盖全部画家，才值得缩短
            if (r - l + 1 < bestLen) {         // 严格小于：同长度保留先出现的（a 更小）
                bestLen = r - l + 1;
                bestL = l; bestR = r;
            }
            if (--cnt[a[l]] == 0) --have;      // 移出左端点；减到 0 说明这个画家没了
            ++l;
        }
    }

    cout << bestL << " " << bestR << "\n";
    return 0;
}

答案有明显单调性：若某个 k 可行，那么所有更大的 k 也可行。所以可以二分 k，把“求最小可行 k”转成 N 次“判定 k 行不行”。

check(k)：贪心地扫一遍，cur 表示当前段的和，装不下（cur + Aᵢ > k）就新开一段。得到的段数 cnt 就是“每段和 ≤ k”时能划分出的最少段数。

为什么 cnt ≤ M 就等于可行：题目要求恰好 M 段。如果 cnt 小于 M，因为 M ≤ N，总可以把某些段再切开（切开只会让每段和更小），补到恰好 M 段。所以判定条件是 cnt ≤ M。

贪心为什么给出最少段数：对任意可行划分，前 i 段覆盖到的位置不会超过贪心的前 i 段；归纳一次就得到贪心段数最少。

边界：lo = max(Aᵢ)，因为 k 连最大的一个数都装不下时必然不可行；hi = ΣAᵢ，全部放一段一定可行。

类型：ΣAᵢ ≤ 10⁵ × 10⁸ = 10¹³，远超 int，全程 long long。复杂度 O(N log ΣA) ≈ 10⁵ × 44。

#include <bits/stdc++.h>
using namespace std;

int n, m;
long long a[100005];

// check(k)：每段和都不超过 k 时，最少要分成几段
bool check(long long k) {
    long long cur = 0;
    int cnt = 1;                       // 至少一段
    for (int i = 1; i <= n; ++i) {
        if (cur + a[i] > k) {          // 当前段装不下 -> 另起一段
            ++cnt;
            cur = a[i];
        } else {
            cur += a[i];               // 能塞就塞：段数才会最少
        }
    }
    return cnt <= m;                   // 段数不超过 m 即可：多出来的段可以继续拆
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    long long sum = 0, mx = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
        mx = max(mx, a[i]);
    }

    long long lo = mx, hi = sum;       // 下界：最大的单个数；上界：全部放一段
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid;      // mid 可行 -> 答案不超过 mid
        else lo = mid + 1;             // mid 不可行 -> 答案必然更大
    }
    cout << lo << "\n";
    return 0;
}

状态：f[i][j] = 从 (i, j) 出发能经过的最多格子数（含自己）。

转移：f[i][j] = 1 + max{ f[nx][ny] }，其中 (nx, ny) 与 (i, j) 相邻、在界内、且高度更低；四周没有更低的格子时 f[i][j] = 1。

因为高度严格递减，转移关系不可能成环，可以放心递归。

记忆化：f 的初值 0 表示“还没算过”。进入 dfs 先查表，算完再存表。每个格子只会真正计算一次，之后都是 O(1) 返回。

答案 = 所有 f[i][j] 的最大值，因为起点任意。

复杂度：状态 R×C ≤ 10⁴ 个，每个状态看 4 个方向，总 O(RC) = 4×10⁴ 次操作。不加记忆化则是每个格子都搜一遍，最坏路径长度 10⁴，总量级不可接受。

#include <bits/stdc++.h>
using namespace std;

int r, c;
int h[105][105];                     // 高度
int dp[105][105];                    // dp[i][j]：从 (i,j) 出发的最长滑坡长度；0 表示还没算
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int dfs(int x, int y) {
    if (dp[x][y]) return dp[x][y];   // 算过就直接给：没有这一行就是指数级搜索
    int best = 1;                    // 至少包含自己这一格
    for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > r || ny < 1 || ny > c) continue;   // 越界
        if (h[nx][ny] < h[x][y])                              // 严格更低才能滑过去
            best = max(best, dfs(nx, ny) + 1);
    }
    return dp[x][y] = best;          // 先存表再返回，下次 O(1)
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> r >> c;
    for (int i = 1; i <= r; ++i)
        for (int j = 1; j <= c; ++j)
            cin >> h[i][j];

    int ans = 0;
    for (int i = 1; i <= r; ++i)
        for (int j = 1; j <= c; ++j)
            ans = max(ans, dfs(i, j));   // 起点任意，全试一遍

    cout << ans << "\n";
    return 0;
}