题解 | #购物单#

#include <bits/stdc++.h>
using namespace std;

vector<int> lis (vector<int>& vec) {
    // 输出以每个元素结尾的最长递增子序列的长度，子序列不需要连续
    vector<int> dp(vec.size(), 0);
    // 利用担心和二分查找的方法求最长递增子序列的长度
    // 思想是如果要让递增子序列尽可能长，就要让递增子序列增加的越来越缓慢，方法是替换掉第一个比当前元素大的值
    // 这个动规问题的原问题是以最后一元素为结尾的最长递增子序列长度，那么较小子问题就是以倒数第二个元素为结尾的最长递增子序列长度
    // 状态转移方程便是，当前元素与当前最长递增子序列中的最后一个元素比较，如果大于最后一个元素，那当前元素当然应该加入最长递增子元素的末尾
    // 如果小于的话，就应该替换掉最长递增子序列中第一个大于当前元素的位置处的元素，这样使得最长递增子序列增速尽量缓
    vector<int> lisvec;
    lisvec.push_back(vec[0]);  // lisvec保存当前的最长递增子序列（在遍历数组过程中），要使当前递增子序列尽可能地缓
    dp[0] = 1;  // dp数组保存以vec[i]结尾的最长递增子序列的长度
    for (int i = 1; i < vec.size(); i++) {
        if (vec[i] > lisvec.back()) {
            lisvec.push_back(vec[i]);
            
        } else {
            auto it = lower_bound(lisvec.begin(), lisvec.end(), vec[i]);
            lisvec[it - lisvec.begin()] = vec[i];
            
        }
        dp[i] = lisvec.size();
    }
    return dp;  // 返回表示以元素vec[i]为结尾的最长递增子序列长度的动规数组
}

int main() {
    // the longest increasing subsequence的变形问题
    // 需要求出以每个元素结尾的最长递增子序列的长度
    // 需要逆序的求出以每个元素为开头的右侧最长递减子序列的长度，这个问题同样可以转化为最长递增子序列的问题
    // 方法是将数组反转
    int num;
    while (cin >> num)
    {
        vector<int> vec;
        int tmp;
        while (num--) {
            cin >> tmp;
            vec.push_back(tmp);
        }
        vector<int> lislen = lis(vec);  // 以vec[i]为结尾的最长递增子序列的记录数组
        reverse(vec.begin(), vec.end());
        vector<int> relislen = lis(vec);
        reverse(relislen.begin(), relislen.end());//  // 转变为以vec[i]为开头的最长递减子序列的记录数组
        
        vector<int> sumvec(vec.size(), 0);  // vec[i]的左右递增递减最长子序列之和-1（除去重复的该元素本身）
        for (int i = 0; i < vec.size(); i++) {
            sumvec[i] = lislen[i] + relislen[i] - 1;
        }
        int maxval = INT_MIN;
        for (int val : sumvec) {
            maxval = max(maxval, val);
        }
        cout << vec.size() - maxval << endl;  // 需要注意求的出列的人数，而不是合唱队的最大人数
    }
    return 0;   

}