双状态dp
对于第i个景点为终点的子序列,当我们遍历它之前任意景点j的时候,我们可以按照两种情况来考虑:
-
如果高度i > 高度 j, 且我们想要延长我们的子序列,来得到一个更长的解,那么我们正在考虑的这个子序列必须是严格上升的。因为题目里要求的是一旦下降,就不能再开始上升。
-
如果高度i < 高度 j, 且我们想要延长我们的子序列,来得到一个更长的解,那么以j为终点的子序列有两种可能:
– case1: 严格上升的,即队伍还没有开始往下走
– case2: 先严格上升,再严格下降,即队伍已经开始往下走了(队伍从头开始一直在往下走也包括在这种情况里面)
这样我们可以维护两个dp数组
dp_inc[i] : 表示以第i个景点为终点的最长严格单调上升子序列的长度
dp_dec[i] : 表示以第i个景点为结束的最长子序列的长度,这个子序列先严格上升,再严格下降。其中严格上升的部分,长度大于等于0。严格下降的部分,长度大于等于1
状态转移:
- 对于j < i, 高度i > 高度 j: dp_inc[i] = dp_inc[j]+1 // 常规单调上升子序列
- 对于j < i, 高度i < 高度 j: dp_dec[i] = max(dp_inc[j]+1, dp_dec[j]+1) // dp_inc[i]+1 对应上面case 1, dp_dec[j]+1 对应上面case 2
最终的结果就是这两个数组的所有值的最大值。
时间复杂度
$O(n^2)$
C++ 代码
#include <iostream>
using namespace std;
const int N = 1010;
int h[N];
int dp_inc[N];
int dp_dec[N];
int main()
{
int n;
cin >> n;
int res = 0;
for(int i = 0; i < n; ++i)
{
cin >> h[i];
dp_inc[i] = 1, dp_dec[i] = 1;
for(int j = 0; j < i; ++j)
{
if(h[j] < h[i])
dp_inc[i] = max(dp_inc[i], dp_inc[j]+1);
if(h[j] > h[i])
dp_dec[i] = max(dp_dec[i], max(dp_inc[j]+1, dp_dec[j]+1));
}
res = max(res, max(dp_inc[i], dp_dec[i]));
}
cout << res << endl;
return 0;
}
在h[j] > h[i]时,为什么dp_inc[j]要+1呢?
这个时候h[i]可以接在h[j]的上升子序列后面,作为第一个下降的山头