最长上升子序列模型 闫氏dp法

题意 可以沿途参观景点 也就是 除了上山 下山也有 即

以一个景点为参考系 向下加向上沿途景点数量最多的答案

换句话说 就是 假设现在走到了k点 那么就是 上山方向以k结尾的最长上升子序列 加上 下山方向以k结尾的最长下降子序列 和 就是答案拉 是不是很简单

Code:

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long  // 个人习惯 有备无患
using namespace std;
const int N = 1100;
int n , a[N] , f[N] , g[N];  //a为提给数据数组 f , g为动态规划数组
int ans; // 记录答案

signed main()
{
    cin >> n;
    for (int i = 1 ; i <= n ; i ++ ) cin >> a[i];

    for (int i = 1 ; i <= n ; i ++ ) 
    {
        f[i] = 1; //初始化为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); //状态转移 反向最大上升子序列
    }

    for (int i = 1 ; i <= n ; i ++ ) ans = max(ans , f[i] + g[i] - 1); //一定要 减一 因为f和g都被初始化为1 也就是 最后答案统计的时候 每个起点都是 统计了两次 故需要减一

    cout << ans << endl;
    
    return 0;
}