3051: 登山 DP

解题思路:双向DP 从左至右上升， 从右至左下降

注意事项:重复计算一个顶点， 结果减一

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int a[N],f[N],g[N];
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= n; i ++)
	{
		f[i] = 1;
		for(int j = 1; j < i; j ++){
			if(a[j] < a[i])
				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[j] < a[i])
				g[i] = max(g[i], g[j] + 1);
		}
	}
	int res =  0;
	for(int i = 1; i <= n; i ++) if(res < f[i] + g[i]) res = f[i] + g[i];
	cout << res - 1 ;
	return 0;
}