| 描述 |
计算最少出列多少位同学，使得剩下的同学排成合唱队形 说明： N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
|
|---|---|
| 知识点 | 循环 |
| 运行时间限制 | 0M |
| 内存限制 | 0 |
| 输入 | 整数N 一行整数，空格隔开，N位同学身高 |
| 输出 | 最少需要几位同学出列 |
| 样例输入 | 8 186 186 150 200 160 130 197 200 |
| 样例输出 | 4 |
1.以每一个成员为中值，计算每个成员的最长正序和逆序合唱队队列人数，最终得到最大序列和元素。计算复杂度O(N^3)；
2.对成员排序，正序和逆序各一次，采用动态规划思想，求各元素对于两个序列的最长公共子序列的和。计算复杂度O(NlogN)+O(N^2) = O(N^2)；
3.采用动态规划的思想，对序列求解最长递增子序列和最长递减子序列；
4.计算每一个元素为中值，计算前向递增最优解和后向递减最优解，得到最终最长最优解；
代码：
#include <iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> A,B,C;
int s;
cin >> s;
if(s == 0)
return 0;
int temp;
for(int l = 0;l < s;l++){
cin >> temp;
A.push_back(temp);
C.push_back(1);//对应每一点，以改点为结尾的増序的子序列的长度
B.push_back(1);//<span style="font-family: 'Times New Roman';">对应每一点，以改点为头的减序的子序列的长度</span>
}
for(int i = 1;i < s;i++)
{
for(int j = 0;j < i;j++){
if(A[i] > A[j] && C[i] < C[j] + 1)
C[i] = C[j] + 1;
}
}
for(int m = s-2;m >= 0;m--)
for(int n = s-1;n > m;n--)
if(A[m] > A[n] && B[m] < B[n]+1)
B[m] = B[n]+1;
int maxl = B[0]+C[0];
for(int k = 0;k < s;k++){
if(maxl < B[k]+C[k])
maxl = B[k]+C[k];
}
cout << s-maxl+1 << endl;
return 0;
}