More Cow Photos

GitHub跳转原题关系图返回列表

从最高出现身高作为中心开始，较低身高只有出现至少两次时才能贡献左右一对。

OJ: usaco

题目 ID: 1516

难度:普及-

标签:贪心统计构造usaco

日期: 2026-07-11 14:51

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定 NN 头奶牛的身高，可以删除一些奶牛，并重新排列剩下的奶牛。要求照片中的身高序列同时满足：

  1. 先不下降再不上升，也就是山形。
  2. 相邻两头奶牛身高不同。
  3. 左右对称。

求最多能留下多少头奶牛。

注意本题题面翻译里第三条容易丢失，原题还有“左右对称”这个条件，也就是关于中间位置镜像的两头奶牛身高相同。

思路

先看一个可以直接验证想法的朴素解：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 14:51
 * update_at: 2026-07-11 14:57
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int T;
int n;
int cnt[MAXN];        // cnt[h] 表示身高 h 的奶牛数量。
int choose_h[MAXN];   // choose_h[h] = 1 表示选择身高 h 出现在照片中。
int ans;

bool check() {
    int center = 0;
    for (int h = n; h >= 1; h--) {
        if (choose_h[h] == 1) {
            center = h;
            break;
        }
    }

    if (center == 0) return false;
    if (cnt[center] == 0) return false;

    for (int h = 1; h <= n; h++) {
        if (choose_h[h] == 0 || h == center) continue;
        if (cnt[h] < 2) return false;
    }

    return true;
}

int calc_answer() {
    int center = 0;
    int value = 0;

    for (int h = n; h >= 1; h--) {
        if (choose_h[h] == 1) {
            center = h;
            break;
        }
    }

    for (int h = 1; h <= n; h++) {
        if (choose_h[h] == 0) continue;
        if (h == center) value += 1;
        else value += 2;
    }

    return value;
}

void dfs(int h) {
    if (h == n + 1) {
        if (check()) {
            int value = calc_answer();
            if (ans < value) ans = value;
        }
        return;
    }

    // 这一层决定“身高 h 是否出现在最终照片中”，只适合小 n。
    choose_h[h] = 0;
    dfs(h + 1);

    choose_h[h] = 1;
    dfs(h + 1);
}

void solve_one() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cnt[i] = 0;
        choose_h[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        int h;
        cin >> h;
        cnt[h]++;
    }

    ans = 0;
    dfs(1);

    cout << ans << '\n';
}

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

    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

这个暴力把每一种身高看成一个 01 选择：choose_h[h] = 1 表示让身高 h 出现在照片中。递归先生成完整选择，再检查最高被选身高能否作为中心，其它被选身高是否都至少出现两次。

合法照片是左右对称的山形，所以中间一定是一个最高身高。除中心外，每个被使用的身高都要在左右两边各出现一次。

因此结构可以看成：

text
低一些的身高 ... 中心最高身高 ... 低一些的身高

中心应该选当前所有奶牛中最高的可用身高。这样不会吃亏，因为中心越高，能放在两边的较低身高只会更多，不会更少。

中心确定后，每个更低的身高互不影响：

  • 如果这个身高出现至少 2 次，就可以放在左右两边，贡献 2。
  • 如果这个身高只出现 1 次，就不能加入，否则无法满足左右对称。
  • 如果这个身高出现很多次，也最多贡献 2，因为同一侧再放一个相同身高会造成相邻相同。

所以满分做法就是统计每个身高出现次数，然后从高到低扫描。第一次遇到的非空身高贡献中心 1 头，之后每个出现次数至少为 2 的较低身高贡献 2 头。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 14:51
 * update_at: 2026-07-11 14:57
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int T;
int n;
int cnt[MAXN]; // cnt[h] 表示身高 h 的奶牛数量。

void solve_one() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cnt[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        int h;
        cin >> h;
        cnt[h]++;
    }

    int ans = 0;
    bool has_center = false;

    // 从高到低扫。最高出现的身高只能放中间，较低身高需要成对放两边。
    for (int h = n; h >= 1; h--) {
        if (cnt[h] == 0) continue;

        if (!has_center) {
            ans++;
            has_center = true;
        } else if (cnt[h] >= 2) {
            ans += 2;
        }
    }

    cout << ans << '\n';
}

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

    cin >> T;
    while (T--) {
        solve_one();
    }

    return 0;
}

复杂度

每个测试用例统计身高需要 O(N)O(N)，从高到低扫描也需要 O(N)O(N)。

所以总时间复杂度为 O(∑N)O(\sum N)，空间复杂度为 O(N)O(N)。

总结

本题关键不是模拟排列，而是先看清合法照片的结构：左右对称加山形，意味着只有一个中心，其余身高都必须左右成对。

从最高身高开始贪心选择中心后，剩下的每个较低身高只需要看出现次数是否至少为 2。