<—点个赞吧QwQ

宣传一下算法提高课整理

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式

第一行包含整数N，表示景点数量。

第二行包含N个整数，表示每个景点的海拔。

输出格式

输出一个整数，表示最多能浏览的景点数。

数据范围

$2 \le N \le 1000$

输入样例：

8
186 186 150 200 160 130 197 220

输出样例：

4

思路1

这题可以分为两个部分：先求最长上升部分，再求下降部分。
所以这题可以用最长上升子序列的思路进行求解。
注意下降部分是要以某一个点为第一个数！！！

代码1

#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N],g[N];
int main () {
    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[i] > a[j]) g[i] = max (g[i],g[j] + 1);    //g[i]表示以第i个数为最长下降子序列的第一个数
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) ans = max (ans,f[i] + g[i] - 1); //减去重叠部分
    cout << ans << endl;
    return 0;
}

思路2

这里我们可以用状态机模型来做。
闫氏$\text{DP}$分析法：
状态表示：$f_{i,k}$，其中$k=0/1$，当$k=0$时表示当前正在往上走，$k=1$时表示当前正在往下走

• 集合：以第$i$个位置作为当前子序列的右端点，且当前状态为$j$
• 属性：$\max$

状态计算：

• 如果当前正在上升，那么这种状态可以由还在上升的状态得来
• 如果当前正在下降，那么这种状态可以由上升的状态或下降的状态得来
• 所以状态转移方程就是
  • $f_{i,0}=f_{i-1,0}+1$
  • $f_{i,1}=\max\lbrace f_{i-1,0},f_{i-1,1}\rbrace+1$

答案：

• 跟最长上升子序列相同，答案就是$\underset{1 \le i \le n}\max\lbrace f_{i,0},f_{i,1} \rbrace$

代码2

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,ans = 0;
int a[N],f[N][2];
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) {
        f[i][0] = f[i][1] = 1;
        for (int j = 1;j < i;j++) {
            if (a[j] < a[i]) f[i][0] = max (f[i][0],f[j][0]+1);
            else if (a[j] > a[i]) f[i][1] = max (f[i][1],max (f[j][0],f[j][1])+1);
        }
    }
    for (int i = 1;i <= n;i++) ans = max (ans,max (f[i][0],f[i][1]));
    cout << ans << endl;
    return 0;
}