https://www.acwing.com/problem/content/1016/
概述
条件
1. 只浏览编号高的景点
2. 不会连续浏览海拔相同的景点
3. 一旦决定下山就不再向上走了(下山,就说明到山顶了,不再观光景了??)
目标
求最多能浏览多少景点?
题解
条件3理解出错,实际上的意思是先上升再下降,这种情况下需要根据题意进行推断
于是最终的感觉就是,先严格上升再严格下降
所有形状是上面的子序列
一种想法是完全使用前面的结论,思考如何套用前面的结论。
两个单独,然后再进行相加,因为两边都是独立的
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N], f[N], g[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++) { // 本身就是严格递增的结果
f[i] = 1;
for (int j = 1; j < i; j ++)
if (a[i] > a[j])
f[i] = max(f[i], f[j] + 1);
}
for (int i = n; i >= 1; i --) {
g[i] = 1;
for (int j = n; j > i; j --)
if (a[i] > a[j])
g[i] = max(g[i], g[j] + 1);
}
int res = 0;
for (int i = n; i >= 1; i --) res = max(res, f[i] + g[i] - 1);
printf("%d\n", res);
return 0;
}