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

题目链接：

思路：

题目意思，找出最少的同学出列，保证学生 1-t 上升， t-n 下降。我们只要求出每个点的最长上升子序列和最长不上升子序列，然后总人数-最长上升子序列和最长不上升子序列+1，就是最少同学出列。

代码：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 110;int n, arr[N];
int dp[N], g[N];signed main(){cin >> n;for(int i =1; i <= n; i++) cin >> arr[i];//上升for(int i = 1; i <= n; i++){dp[i] = 1;for(int j = 1;  j< i; j++){if(arr[j] < arr[i]){dp[i] = max(dp[i], dp[j]+1);}}}//下降for(int i = n; i >=1; i--){g[i] = 1;for(int j =n; j > i; j--){if(arr[j] < arr[i]){g[i] = max(g[i], g[j]+1);}}}//找到最长上升子序列和最长不上升子序列数量int ans = 0;for(int i =1; i <= n; i++){ans = max(ans, g[i]+dp[i]);}cout << n - ans +1<< endl;return 0;
}