动态规划

应用动态规划解决队列问题

问题描述

计算最少出列多少位同学,使得剩下的同学排成合唱队形说明:N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足存在i(1<=i<=K)使得T1Ti+1>……>TK。
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。

示例1

8
186 186 150 200 160 130 197 200

输出

4

求解思路

  1. 通过动态规划求解每个字符结尾的最大递增子字符串的长度,
  2. 再反转数组,
  3. 按照 1.步骤再进行一次
  4. 两次叠加最大值减一即为最后队列的长度
    代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    #include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
    vector<int> dp(vector<int> &input,int n){
    vector<int> list_(n,1);
    for(int i=1;i<=n;i++)
    for(int j=i-1;j>=0;j--){
    if(input[i]>input[j])
    list_[i]=max(list_[i],list_[j]+1);
    }
    return list_;
    }
    int main(){
    int n;
    while(cin>>n){
    vector<int> input(n);
    for(int i=0;i<n;i++){
    cin>>input[i];
    }
    vector<int> front = dp(input,n);
    reverse(input.begin(),input.end());
    vector<int> back = dp(input, n);
    int max_ = 0;
    for(int i=0;i<n;i++){
    int temp =front[i]+back[n-i-1];
    if(temp>max_) max_=temp;
    }
    cout<<(n-(max_-1))<<endl;
    }
    return 0;

    }