题目：合唱队形（蓝桥OJ 0724）

本文主要是介绍题目：合唱队形（蓝桥OJ 0724），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

---

解题思路： 

        LIS的拓展，枚举i，以i位置为最长上升子序列的终点、最长下降子序列的起点。将上升与下降的值相加得以i位置为最高点得队形总人数。最后比较每个i位置（1~n）总人数的大小得最大队形总人数，最小剩下人数 = 全部同学数 - 最大队形总人数。

---

题解：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e2 + 9;
int a[N], dpl[N], dpr[N];int main()
{int n;cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];for(int i = 1; i <= n; i++){dpl[i] = 1;for(int j = 1; j < i; j++){if(a[i] > a[j])dpl[i] = max(dpl[i], dpl[j] + 1); }}for(int i = n; i >= 1; i--)  // 反过来以n为起点找最长上升子序列<=>以i为起点的最长下降子序列{dpr[i] = 1;for(int j = n; j > i; j--)  // j的方向不会影响dp,只需要关心范围即可{if(a[i] > a[j])dpr[i] = max(dpr[i], dpr[j] + 1);}}  int ans = n;for(int i = 1; i <= n; i++)ans = min(ans, n - (dpl[i] + dpr[i] - 1));  cout << ans << '\n';return 0;
}

---

知识点：​​​​​​​LIS

这篇关于题目：合唱队形（蓝桥OJ 0724）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---