洛谷P1091合唱队形（最长上升子序列）

n 位同学站成一排，音乐老师要请其中的 $n-k$ 位同学出列，使得剩下的 $k$ 位同学排成合唱队形。

合唱队形是指这样的一种队形：设 $k$ 位同学从左到右依次编号为 1,2, … ,k，他们的身高分别为 t_1,t_2, … ,t_k，则他们的身高满足 t_1t_{i+1}> … >t_k。

你的任务是，已知所有 n 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

## 输入格式

共二行。

第一行是一个整数 n（2 <=n <= 100），表示同学的总数。

第二行有 n 个整数，用空格分隔，第 i个整数 t_i（130<= t_i <=230）是第 i 位同学的身高（厘米）。

## 输出格式

一个整数，最少需要几位同学出列。

 样例输入 #1
8
186 186 150 200 160 130 197 220

## 提示

对于 50% 的数据，保证有n <= 20。

对于全部的数据，保证有 n <= 100。

在讲这道题之前，先来讲一下最长上升子序列：

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

假设我们有7个数，分别为3 1 2 1 8 5 6，那么他的最长上升子序列应该为1 2 5 6

所以答案为4。

现在来讲一讲这道题目用代码应当如何实现。

首先，这是一道动态规划的题目，我们用集合的方式进行分析

 我们是要求最长上升子序列，所以集合的属性应该是MAX，这里的状态计算我来解释一下。

我们已经确定，该最长上升子序列中的最后一位数已经确定，那么我们所找到的该序列中的倒数第二个数应该有 i 种可能。这里 0 代表这个上升子序列中没有倒数第二个数,(即 f[i] 为上升子序列中的唯一的一个数)。其他的1 ， 2 ， 3 表示 f[i] 的前一个数为提供的数组中的第 i 个数。

假设这 f[i] 的前一个数是 f[j] ， 因为是上升子序列 ， 所以 f[j] < f[i]

因此，当满足上述条件时，f[i] = max(f[i] , f[j] + 1)。

最后我们再次遍历一遍 f[i] 找到以 f[i]结尾最长的上升子序列。

这里我们先来coding

动态规划主要难的点在于理解思路，代码量和难度其实是比较小的

#include #include #include using namespace std;const int N = 10010;int n;int num[N] , dp[N];int main(){    cin >> n;    for (int i = 0; i > num[i];    for (int i = 0; i < n; i ++ ){ dp[i] = 1; for(int j = 0 ; j  num[j]){  dp[i] = max(dp[i] , dp[j] + 1);     } }    }    int res = 0;    for (int i = 0; i < n; i ++ ) res = max(res , dp[i]);    cout << res;    return 0;}

#include #include #include using namespace std;const int N = 110;int n;int g[N] , f[N] , a[N];int main(){    cin >> n;    int res = 0;    for(int i = 1 ; i >a[i];//从左向右的最长上升子序列    for(int i = 1 ; i <= n ; i ++){ g[i] = 1; for(int j = 1 ; j  a[j]) g[i] = max(g[i] , g[j] + 1); }    }//从右向左的最长上升子序列    for(int i = n ; i >= 1 ; i --){ f[i] = 1; for(int j = n ; j > i ; j --){     if(a[i] > a[j]) f[i] = max(f[i] , f[j] + 1); }    }    for(int i = 1 ; i <= n ; i ++){ res = max(res , g[i] + f[i] - 1);    }    cout << n - res;    return 0;}