# POJ 1836 LIS
[POJ-1836](http://poj.org/problem?id=1836)
## 题目分析
题目让我们求出使一个给定向量变成一个从每个元素出发的左右两部分中都至少有一部分构成递减向量的新向量最少需要删除的元素数. 即这样:
```text
+ ++ +
++ ++++
+++++++
```
变成这样:
```text
++
+ +++
+ +++
```
易知, 最终结果是一个单峰(或无峰)形状的子序列. 那么我们自然可以想到, 峰值的左右两边都尽可能长, 则需要删除的元素就尽可能少. 将问题转变为(峰值 + LIS)两个子问题即可求解.
1. 这里所说的LIS, 由于除边界外每个元素都有左右两边, 所以必须求从左至右和从右至左两个方向的解.
2. 最优解可能有两个相等的峰值(一个代表向左看部分, 另一个代表向右看的部分), 并且这两个峰值在原向量中并不一定相邻(如3 4 5 1 2 5 4 3这组数据), 若想找到此类数据的正确解答, 最好写的方法是遍历每个<元素, 元素>对, 使其分别作为向左看和向右看的峰值.
## 代码(C++)
```c++
#include <iostream>
using namespace std;
int main(){
double a[1005];
int n, dp1[1005], dp2[1005];
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
dp1[i] = dp2[i] = 1;
}
// 求每个元素从左至右的最长上升子序列
for(int i = 1; i <= n; i++){
for(int j = 1; j < i; j++){
if(a[j] >= a[i]) continue;
if(dp1[j] + 1 > dp1[i])
dp1[i] = dp1[j] + 1;
}
}
// 求每个元素从右至左的最长上升子序列
for(int i = n; i >= 1; i--){
for(int j = n; j >= i; j--){
if(a[j] >= a[i]) continue;
if(dp2[j] + 1 > dp2[i])
dp2[i] = dp2[j] + 1;
}
}
// 为每个从左至右和从右至左的上升子序列配对
// 找到最优解
int maxn = -1;
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++)
maxn = max(maxn, dp1[i] + dp2[j]);
}
cout << n - maxn << endl;
return 0;
}
```
![]()