问题描述

小椒是个摄影爱好者。恰逢班级合照，他受邀帮忙拍照（站成一排）。这本是一件简单的事，但由于啾啾是个完美主义者，他希望他拍的照片必须符合美学，即存在一个身高较大值，使得较大值无论是往左还是往右身高都是递减的（数学表示应为：a[1]≤...≤a[i]≥a[i+1]≥...≥a[n]）。同学们已经站好了，但站位不符合美学，你需要找出尽可能少的同学出队进行重新排列。请问最少需要出队多少个同学？

输入格式

第一行输入 n，表示有 n 个同学。

接下来的 n 行输入校友身高，其中第 i 行输入 a[i](1≤i≤n)，表示编号为 ii 的校友的身高（单位：毫米）。

(1≤n≤100,1500≤a[i]≤1900)。

输出描述

输出一个整数，表示最少需要出队多少个同学。

样例输入

6
1700 1701 1702 1703 1704 1705

样例输出

0

题解

最长非递减（增）子序列的问题 

对于每一个i，维护在位置i的从1到i最长非递减子序列长度和从i到n非递增子序列的长度

枚举每一个位置的和，总数减去这个和得到的最小值为答案

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 105;int a[N], up[N], down[N];int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n;cin >> n;for(int i = 1;i <= n;i ++)cin >> a[i];for(int i = 1;i <= n;i ++)up[i] = down[i] = 1;for(int i = 2;i <= n;i ++)for(int j = 1;j <= i - 1;j ++){if(a[i] >= a[j])up[i] = max(up[i], up[j] + 1);}for(int i = n - 1;i >= 1;i --){for(int j = n;j >= i + 1;j --)if(a[i] >= a[j])down[i] = max(down[i], down[j] + 1);}
//	for(int i = 1;i <= n;i ++)cout << up[i] << ' ';
//	cout << '\n';
//	for(int i = 1;i <= n;i ++)cout << down[i] << ' ';
//	cout << '\n';int ans = 0x3f3f3f3f;for(int i = 1;i <= n;i ++)ans = min(ans, n - (up[i] + down[i]) + 1);cout << ans << '\n';return 0;
}

写最长非递减子序列初始化时，必须将每一个点的值初始化为1。