Oiclass P1227 题解

这道题需要两次动规 (LIS DP)

OK，再再再再是经典的五步

1. 划分状态

在这道题，我用每个人划分状态，每个人有两个状态，分别是以这个人结尾的最长不下降子序列长度和以这个人开头的最长不下降自序列的长度

2. 确定状态和状态变量

我使用三个数组 \(a,\ b,\ c\) 分别：存储输入的数据、存储状态一（以这个人结尾的最长不下降子序列长度）、存储状态二（以这个人开头的最长不下降自序列的长度）。状态如上

3. 确定决策并写出状态转移方程

决策很简单，就按最长不下降自序列（LIS）长度计算的方法来回算两边就可以算出两种状态了（状态的定义见上文），两种状态分别放在数组 \(b,\ c\) 之中。状态转移方程： \[ \begin{array}{lr} 0<j≤n\\ b_i=\max(b_i,b_j+1) \\ c_i=\max(c_i,c_j+1)\\ \end{array} \]

4. 边界条件

\[ b_i=c_i=1 \]

5. 实现

代码实际上很简单，一次正序的 LIS 和一次倒叙的 LIS 就可以求出所有状态，再来比较哪一个人左右两边正确排序的人最多（\(ans=\max(ans,\ b_i+c_i-1)\)），输出即可，代码如下：

#include <iostream>

using namespace std;

int n, ans, a[109], b[109], c[109];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = c[i] = 1;
    }
    for (int i = n - 1; i >= 1; i--) {
        for (int j = n; j >= i - 1; j--) {
            if (a[i] > a[j]) {
                b[i] = max(b[i], b[j] + 1);
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (a[i] > a[j]) {
                c[i] = max(c[i], c[j] + 1);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        ans = max(b[i] + c[i] - 1, ans);
    }
    cout << n - ans << endl;
}