题解 | #合唱队#

状态转移方程：

考虑每人的添加与否，下个人与当前或者上个人进行比较。因此，当前人是否考虑，会影响到 有效队列末尾的身高、有效队列人数这两个要素。

因此，f[i][j]可以为前i个人形成的有效队列中，队尾身高为j的总人数；也可以为前i个人形成的有效队列中，总人数为j时队尾的身高。

代码尝试如下：

（1）

考虑顶峰来自于n个数中，因此遍历n个数，将其作为顶峰；

对每个顶峰dp，f[j][k]表示前i个数队列，末尾元素j的次数。

分在顶峰左侧、顶峰、顶峰右侧进行dp.

<15%通过率>

（2）

看题解，自己的思路比较复杂了。

问题：方法_1进行了n次二维dp，且当前dp的结果可能被下次dp使用

因此，对递增、递减进行二次二维dp。

<15%通过率>

dp数组初始值0 和 当前值0影响。将该种情况嵌入后

<20%通过率>

数值上限设置维1000，修改为hei_max+1之后

<45%通过率> - 内存超限

(3)

针对方法_进行优化。

使用一个数组，处理递增、递减的二次二维dp。

<65%通过率>

将j由队列的末尾值修改为元素个数，降低dp数组范围

<95%通过率>

f[i]由f[i-1]决定（不考虑j），使用滚动数组。

<100%通过率>

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <vector>

using namespace std;

/***
<sample input>
8
186 186 150 200 160 130 197 200
<sample output>
4
*/

int main() {
    int n;
    cin >> n;
    vector<int> hei(n + 1);
    int hei_max = 0;
    for (int i = 1; i <= n; i++) {
        cin >> hei[i];
        if (hei[i] > hei_max) hei_max = hei[i];
    }

    vector<int> up_rec(n+1, 0);
    // vector<vector<int>> up(n + 2, vector<int>(n + 2,
    //                        0x7f7f));  // n+2因为递减数组，存在n+1的计数
    vector<int> up(n+2, 0x7f7f7f7f);      // up[i]仅与up[i-1]有关，因此使用滚动数组。

    up[0] = 0;   // 这里的j时有效队列的最后一个数，与当前值进行比较
    // f[i][?] == hei[i]，?表示从开头->cur的最大递增长度；
    for (int i = 1; i <= n; i++) {
        vector<int> pre = up;   // 保存前一个状态
        for (int j = 0; j <= n; j++) {
            // 找到上一个阶段的有效值
            if (pre[j] <= hei_max) {
                // 严格递增，或者当前元素为0、队末元素未初始化
                if ((hei[i] == 0 && pre[j] == 0) || hei[i] > pre[j]) {
                    // 取该元素
                    up[j + 1] = min(up[j + 1], hei[i]); // 保存递增顺序的最小值
                    // 不取该元素
                } 
                // 不满足，该元素不可取
                up[j] = min(up[j], pre[j]);
                // printf("i:%d, j:%d, pre[j]:%d, up[j]:%d, up[j+1]:%d\n",
                //         i, j, pre[j], up[j], up[j+1]);
            }
        }

        // dp时候保存之前的结果
        for (int j = 1; j <= n; j++) {
            if (up[j] == hei[i]) {
                up_rec[i] = j;
                // printf("i:%d, j:%d\n", i, j);
                break;
            }
        }
    }

    // // f[i][hei[i]]，此时cur->n的最大递减长度；
    vector<int>& down = up;
    for (int i = 0; i < n + 2; i++) {
        down[i] = 0x7f7f7f7f;
    }

    down[0] = 0;    // down[i]记录前i个数字有效队列的末尾元素，从后向前遍历
    for (int i = n; i >= 1; i--) {
        vector<int> pre = down;     // 记录前一个状态
        // j代表有效递增序列的起始元素
        for (int j = 0; j <= n; j++) {
            // 找到上一个状态(i+1)的有效队列末尾元素 j
            if (pre[j] <= hei_max) {
                // 严格递减
                if ((hei[i] == 0 && pre[j] == 0) || hei[i] > pre[j]) {
                    // 取该元素
                    down[j + 1] = min(down[j + 1], hei[i]);
                }

                // 不满足，该元素不可取
                down[j] = min(down[j], pre[j]);
            }
        }
        for (int j = 1; j <= n; j++) {
            if (down[j] == hei[i]) {
                // down_rec[i-1].push_back(j);
                up_rec[i] += j;
                // printf("i:%d, down_len:%d\n", i, j);
                break;
            }
        }
    }

    // // // 综合递增、递减长度
    int max_len = 0;
    for (int i = 1; i <= n; i++) {
        // int tmp = up_rec[i] + down_rec[i] - 1;
        if (up_rec[i]-1 > max_len) max_len = up_rec[i]-1;
        // printf("i:%d, up[i]:%d, down[i]:%d\n", i, up[i][hei[i]], down[i][hei[i]]);
    }

    cout << n - max_len;
    return 0;
}