AcWing 1014. 登山(由于看不太懂前面几篇题解就自己写了个通俗易懂的)
原题链接
简单
作者:
xeus
,
2021-06-23 17:27:28
,
所有人可见
,
阅读 1014
做两遍DP,求出以i点为结尾的最大上升子序列f[i][0],以i点为起点的最大下降子序列,则可以求出该点作为山顶(即转折点)的最多的景点为f[i][0] + f[i][1] - 1(这里减1是因为i这个点既作为左区间的终点又作为右区间的起点被算进去了两次)
最后遍历一遍所有点算出最大的f[i][0] + f[i][1] - 1 (这个过程可以加在第二次倒序DP中)
C++代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N][2], h[N], ans, n;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
f[i][0] = 1;
scanf("%d", &h[i]);
for (int j = 1; j < i; j ++ )
if (h[i] > h[j]) f[i][0] = max(f[i][0], f[j][0] + 1);
}
for (int i = n; i; i -- )
{
f[i][1] = 1;
for (int j = n; j > i; j -- )
if (h[i] > h[j]) f[i][1] = max(f[i][1], f[j][1] + 1);
ans = max(ans, f[i][0] + f[i][1] - 1);
}
printf("%d\n", ans);
return 0;
}
不是最大哦,是最长
Orz