目录

Alignment （DP基础--最长上升子序列）

题目

题意

删除一些数，使得中间的每个数都比左边或者右边的大。

思路

从左边进行一次LIS,然后从右边进行一次，记录的数组分别为a,b。然后枚举中间的两个数为两个LIS的终点，求出最大值，其为留下来的人,总数减去即可。

代码

#include 
    
     #include 
     
      #include 
      
       #define N 1003using namespace std;double a[N];int d[N], b[N];int main(){    int n;    cin >> n;    for (int i = 0; i < n; i++)        cin >> a[i];    for (int i = 0; i < n; i++)//从左边进行LIS 结果设为 d    {        d[i] = 1;        for (int j = 0; j <= i; j++)        {            if (a[i] > a[j])            {                d[i] = max(d[i], d[j] + 1);            }        }    }    for (int i = n - 1; i >= 0; i--)//从右边进行LIS 结果设为b    {        b[i] = 1;        for (int j = n - 1; j >= i; j--)        {            if (a[i] > a[j])            {                b[i] = max(b[i], b[j] + 1);            }        }    }    int res = 0;    for (int i = 0; i < n; i++)//往中间枚举        for (int j = i+1; j < n; j++)        {            res = max(res, d[i] + b[j]);        }    cout << n-res;}