洛谷 P1091 [NOIP 2004 提高组] 合唱队形

// P1091 [NOIP 2004 提高组] 合唱队形 —— ★ 这一版就能 AC
//
// 题意：n 个人站一排，请走 n-k 位，剩下的 k 位要满足 `t₁ < … < tᵢ > … > t_k`
//       （**严格**上升再**严格**下降，`1 ≤ i ≤ k`）。求最少走几位。
//
// ★ 关键一步：**跑两遍 LIS**。
//   `f[i]` = 以第 i 个人**结尾**的最长严格上升子序列长度（从左往右）；
//   `g[i]` = 以第 i 个人**开头**的最长严格下降子序列长度（从右往左跑一遍 LIS）。
//   枚举「最高的那个人」是第 i 个 ⇒ 队形最长 = `f[i] + g[i] - 1`。
//   答案 = `n − max(f[i] + g[i] - 1)`。
//
// ⚠⚠ **那个 `-1` 是这道题最容易漏的一笔**：第 i 个人在 `f[i]` 和 `g[i]` 里**各被数了一次**
//   （页面第 ③ 步量了漏掉它会怎样）。
//
// ★ 题面写的是 `1 ≤ i ≤ k` ⇒ **单调上升或单调下降本身也是合唱队形**
//   （最高的那个人可以站在最左边或最右边）—— 上面这个式子天然覆盖了这两种情况。
//
// ★★ 这道题的身高范围是 `130 ≤ tᵢ ≤ 230`（只有 101 种），而 `n ≤ 100`
//   ⇒ **`n / 值域 ≈ 1.0`** —— 按同一轮 [P1020](/sol/p1020/) 那条曲线，
//     「严格 / 非严格」那个坑在这道题上**几乎必然现形**（页面第 ④ 步实测）。
//
// 复杂度 `O(n²)`，`n ≤ 100` 绰绰有余。

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

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> t(n);
    for (int& x : t) cin >> x;

    vector<int> f(n, 1), g(n, 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (t[j] < t[i]) f[i] = max(f[i], f[j] + 1);          // ★ 严格上升
    for (int i = n - 1; i >= 0; i--)
        for (int j = n - 1; j > i; j--)
            if (t[j] < t[i]) g[i] = max(g[i], g[j] + 1);          // ★ 严格下降

    int best = 0;
    for (int i = 0; i < n; i++) best = max(best, f[i] + g[i] - 1);   // ★ 减 1
    cout << n - best << "\n";
    return 0;
}

// P1091 的参照物：**枚举所有子集**，逐个检查是不是合唱队形
//
// ★ 它把题面那个不等式链 `t₁ < … < tᵢ > … > t_k` 照抄一遍去验，
//   不需要「跑两遍 LIS」，也不用想那个 `-1`。
// ⚠ 只跑得动 `n ≤ 20` 左右。

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

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> t(n);
    for (int& x : t) cin >> x;

    int best = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        vector<int> v;
        for (int i = 0; i < n; i++) if (mask >> i & 1) v.push_back(t[i]);
        int k = v.size();
        // 找峰：先严格升，再严格降；峰可以在两端
        int p = 0;
        while (p + 1 < k && v[p] < v[p + 1]) p++;
        int q = p;
        while (q + 1 < k && v[q] > v[q + 1]) q++;
        if (q == k - 1) best = max(best, k);              // 整条链都合法
    }
    cout << n - best << "\n";
    return 0;
}

// P1091 错法一：忘了那个 `-1`
//
// 枚举「最高的那个人」是第 i 个时，他在 `f[i]`（左边那段）和 `g[i]`（右边那段）里
// **各被数了一次** —— 不减掉就把他数了两遍。
//
// ★★ 而它错得非常规整：**队形长度恒好 1，于是答案恒少 1**
//   （页面第 ③ 步实测逐组相等）—— 除非 `n - best` 已经被压到 0 以下那种边界。
// ⇒ 「说清楚一个 bug 算了什么」比说它「错了」有用得多。

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

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> t(n);
    for (int& x : t) cin >> x;
    vector<int> f(n, 1), g(n, 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++) if (t[j] < t[i]) f[i] = max(f[i], f[j] + 1);
    for (int i = n - 1; i >= 0; i--)
        for (int j = n - 1; j > i; j--) if (t[j] < t[i]) g[i] = max(g[i], g[j] + 1);
    int best = 0;
    for (int i = 0; i < n; i++) best = max(best, f[i] + g[i]);      // ← 少了 -1
    cout << n - best << "\n";
    return 0;
}

// P1091 错法二：把「严格」写成了「非严格」（`<=` 而不是 `<`）
//
// 题面写的是 `t₁ < … < tᵢ > … > t_k` —— **两边都是严格的**，
// 相邻两个人身高一样是**不允许**的。
//
// ★★ 而这道题的数据让它躲不掉：身高只有 `130 ≤ tᵢ ≤ 230`（**101 种**），而 `n ≤ 100`
//   ⇒ `n / 值域 ≈ 1.0`。按同一轮 [P1020](/sol/p1020/) 那条曲线，
//     比值到 1.0 时这个坑的抓获率已经在 **87%** 上下了（页面第 ④ 步实测）。
//   ⇒ 和 [P1439](/sol/p1439/)（题面保证没有重复 ⇒ 精确的 0）正好是两个极端。
//
// ★ 官方样例里有一对相同的身高（两个 186）—— 第 ④ 步会说它挡没挡住。

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

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> t(n);
    for (int& x : t) cin >> x;
    vector<int> f(n, 1), g(n, 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++) if (t[j] <= t[i]) f[i] = max(f[i], f[j] + 1);   // ← <=
    for (int i = n - 1; i >= 0; i--)
        for (int j = n - 1; j > i; j--) if (t[j] <= t[i]) g[i] = max(g[i], g[j] + 1);
    int best = 0;
    for (int i = 0; i < n; i++) best = max(best, f[i] + g[i] - 1);
    cout << n - best << "\n";
    return 0;
}

// P1091 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1091Count`      人看的版本
// `./p1091Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 四段：
//   ① ★ 「跑两遍 LIS」≡ `2ⁿ` 枚举子集逐个验队形；
//   ② ★★ 忘了那个 `-1` 那版**算了什么**：答案恒少 1（逐组相等）；
//   ③ ★★★ 「严格写成非严格」的抓获率 —— 沿 `n / 身高种类数` 这个比值走一遍，
//      和同一轮 [P1020](/sol/p1020/) 那条曲线是同一条；
//   ④ ★ 题面 `1 ≤ i ≤ k` ⇒ **单调上升或单调下降本身也算队形**：数一数这种局面有多少。

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

static bool CSV = false;
static void row(const char* key, const vector<ll>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (ll x : v) printf(",%lld", x);
    printf("\n");
}

/** 正解：两遍 LIS。loose=true 时把严格换成非严格；minus=false 时忘了 -1 */
static int solve(const vector<int>& t, bool loose = false, bool minus = true, int* peakSide = nullptr) {
    int n = t.size();
    vector<int> f(n, 1), g(n, 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (loose ? t[j] <= t[i] : t[j] < t[i]) f[i] = max(f[i], f[j] + 1);
    for (int i = n - 1; i >= 0; i--)
        for (int j = n - 1; j > i; j--)
            if (loose ? t[j] <= t[i] : t[j] < t[i]) g[i] = max(g[i], g[j] + 1);
    int best = 0, at = 0;
    for (int i = 0; i < n; i++) {
        int cur = f[i] + g[i] - (minus ? 1 : 0);
        if (cur > best) { best = cur; at = i; }
    }
    if (peakSide) *peakSide = (f[at] == 1 ? -1 : (g[at] == 1 ? 1 : 0));   // -1 峰在最左，1 峰在最右
    return n - best;
}
/** 参照物：枚举所有子集，照题面那条不等式链验 */
static int brute(const vector<int>& t) {
    int n = t.size(), best = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        vector<int> v;
        for (int i = 0; i < n; i++) if (mask >> i & 1) v.push_back(t[i]);
        int k = v.size(), p = 0;
        while (p + 1 < k && v[p] < v[p + 1]) p++;
        int q = p;
        while (q + 1 < k && v[q] > v[q + 1]) q++;
        if (q == k - 1) best = max(best, k);
    }
    return n - best;
}
static vector<int> gen(mt19937& rng, int n, int kinds) {
    vector<int> t(n);
    for (int i = 0; i < n; i++) t[i] = 130 + (int)(rng() % (unsigned)kinds);
    return t;
}

int main(int argc, char** argv) {
    CSV = argc > 1 && string(argv[1]) == "csv";

    /* ① 两遍 LIS ≡ 2^n 暴力，② 忘了 -1 那版恒少 1 */
    {
        mt19937 rng(20260829u);
        int groups = 0, bad = 0, offByOne = 0;
        for (int rep = 0; rep < 300; rep++, groups++) {
            vector<int> t = gen(rng, (int)(rng() % 13) + 2, 14);
            int ok = solve(t);
            if (brute(t) != ok) bad++;
            if (solve(t, false, false) == ok - 1) offByOne++;      // 恒少 1
        }
        if (!CSV) printf("① %d 组（n ≤ 14）：两遍 LIS vs 2^n 枚举子集不一致 %d 组\n"
                         "② 忘了 -1 那版：答案**恒好少 1** 的轮数 %d / %d（逐组相等）\n",
                         groups, bad, offByOne, groups);
        row("ref", {groups, bad, offByOne});
    }

    /* ③ ★★★ 「严格写成非严格」的抓获率，沿比值走 */
    {
        const int KINDS[] = {2000, 200, 40, 14, 4};      // n 固定 14 ⇒ 比值 0.007 / 0.07 / 0.35 / 1.0 / 3.5
        vector<ll> out;
        for (int k : KINDS) {
            mt19937 rng(k * 7919u + 91u);
            int dup = 0, caught = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> t = gen(rng, 14, k);
                vector<int> s = t;
                sort(s.begin(), s.end());
                if (adjacent_find(s.begin(), s.end()) != s.end()) dup++;
                if (solve(t, true) != solve(t)) caught++;
            }
            out.push_back(caught); out.push_back(dup);
            if (!CSV) printf("③ n = 14，身高 %4d 种（比值 %.3f）：非严格那版被抓 %d / 300，"
                             "有相同身高的 %d / 300\n", k, 14.0 / k, caught, dup);
        }
        row("loose", out);
    }

    /* ④ 单调上升 / 单调下降本身也算队形 */
    {
        mt19937 rng(4444u);
        int rounds = 300, left = 0, right = 0;
        for (int r = 0; r < rounds; r++) {
            vector<int> t = gen(rng, 14, 14);
            int side = 0;
            solve(t, false, true, &side);
            if (side < 0) left++;
            else if (side > 0) right++;
        }
        if (!CSV) printf("④ %d 轮：最优队形里「最高的人站在最左边」（纯下降）%d 轮，"
                         "「站在最右边」（纯上升）%d 轮 ⇒ 题面 1 ≤ i ≤ k 允许这两种\n",
                         rounds, left, right);
        row("mono", {rounds, left, right});
    }
    return 0;
}

// P1091 对拍生成器：`./p1091Gen <seed> [n 上限] [身高种类数]`
//   默认 `n ≤ 14`、身高从 `130..230` 里取（101 种）—— **照题面的比值**。
//
// ★ 题面是 `n ≤ 100`、`130 ≤ tᵢ ≤ 230`（101 种）⇒ `n / 值域 ≈ 1.0`；
//   默认档 `n ≤ 14` 时把种类数一起缩到 14，比值仍然是 1.0 ——
//   ⇒ 又一次「[照抄题面的比值，不是绝对规模](/sol/p1020/)」（n 小了才能用 `2ⁿ` 暴力当参照物）。

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

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int nHi = argc > 2 ? atoi(argv[2]) : 14;
    int kinds = argc > 3 ? atoi(argv[3]) : 14;
    nHi = max(2, min(100, nHi));
    kinds = max(1, min(101, kinds));

    mt19937 rng(seed * 2654435761u + 1091u);
    int n = (int)(rng() % (unsigned)(nHi - 1)) + 2;
    printf("%d\n", n);
    for (int i = 0; i < n; i++)
        printf("%u%c", 130 + (unsigned)(rng() % (unsigned)kinds), i + 1 == n ? '\n' : ' ');
    return 0;
}