C++ 代码：列车调度问题

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

输入格式： 输入第一行给出一个整数N (2 ≤ N ≤10^5)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式： 在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例： 9 8 4 2 5 3 9 1 6 7

输出样例： 4

代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<int> train(N);
    for (int i = 0; i < N; i++) {
        cin >> train[i];
    }
    
    vector<int> dp(N);
    for (int i = 0; i < N; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (train[j] > train[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    
    int maxTracks = *max_element(dp.begin(), dp.end());
    cout << N - maxTracks << endl;
    
    return 0;
}

解释：

该代码使用动态规划的思想来解决问题。首先读入输入的列车序号并存储在一个向量中。然后，定义一个动态规划的向量dp，其中dp[i]表示以第i个列车为结尾的最长递减子序列的长度。

接下来，使用两个嵌套循环来计算dp数组的值。外层循环遍历每个列车，内层循环遍历该列车之前的列车。对于每对列车i和j，如果列车j的序号大于列车i的序号，则表示列车i可以在列车j的后面出站，因此可以更新dp[i]为dp[j] + 1。最终，dp数组中的最大值即为所需的最少铁轨条数。

最后，输出总的铁轨条数减去最少铁轨条数即为答案。