建设银行佛山分行网站,网站开发4k分辨率,西安seo服务,免费的外链平台问题描述#xff1a; 解题思路#xff1a; LIS的拓展#xff0c;枚举i#xff0c;以i位置为最长上升子序列的终点、最长下降子序列的起点。将上升与下降的值相加得以i位置为最高点得队形总人数。最后比较每个i位置#xff08;1~n#xff09;总人数的大小得最大队形总人数…问题描述 解题思路 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
