n-位同学站成一排音乐老师要请其中的-n-k-位同学出列使得剩下的-k-位同学排成合唱队形。nn合唱队形是指这样的一种队形：设-k-位同学从左到右依次编号为-12-…-k他们的身高分别为-t1t2t3tk-则他们的身高满足-t1titi+1tk-1≤i≤k。nn你的任务是已知所有-n-位同学的身高计算最少需要几位同学出列可以使得剩下的同学排成合唱队形。nn写出c++代码

#include #include using namespace std;

int main() { int n, k; cin >> n >> k; int a[n]; for(int i = 0; i < n; i++) { cin >> a[i]; } int dp1[n], dp2[n];//dp1表示从左到右最长的上升子序列长度，dp2表示从右到左最长的下降子序列长度 for(int i = 0; i < n; i++) { dp1[i] = 1; for(int j = 0; j < i; j++) { if(a[j] < a[i]) { dp1[i] = max(dp1[i], dp1[j] + 1); } } } for(int i = n - 1; i >= 0; i--) { dp2[i] = 1; for(int j = n - 1; j > i; j--) { if(a[j] < a[i]) { dp2[i] = max(dp2[i], dp2[j] + 1); } } } int ans = 0; for(int i = 0; i < n; i++) { if(dp1[i] + dp2[i] - 1 > ans) { ans = dp1[i] + dp2[i] - 1; } } cout << n - ans << endl;//最少需要出列的人数就是总人数减去能够排成合唱队形的人数 return 0; }