<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
1014.登山
五一到了,ACM队组织大家去登山观光,队员们发现山上一共有 $N$ 个景点,并且决定按照顺序来浏览这些景点,即每次所浏览景点的编号都要大于前一个浏览景点的编号
同时队员们还有另一个登山习惯,就是不连续浏览海拔相同的两个景点,并且一旦开始下山,就不再向上走了
队员们希望在满足上面条件的同时,尽可能多的浏览景点,你能帮他们找出最多可能浏览的景点数么?
输入格式
第一行包含整数 $N$,表示景点数量。
第二行包含 $N$ 个整数,表示每个景点的海拔。
输出格式
输出一个整数,表示最多能浏览的景点数。
数据范围
$2 \le N \le 1000$
根据题意,很明显可以先尝试 线性dp 来解决
再观察上山下山的过程,上山可以对应的为求 上升子序列,下山就是求 下降子序列
题目要求最长的子序列。考虑如何将两种子序列的答案合并来求解
本题解中我们用 最长上升(下降)子序列模型 来解决
方案:线性dp 复杂度:$O(n ^ 2)$:
状态表示
$f[i]$ 表示以第 $i$ 个位置作为当前子序列的右端点的值
$g[i]$ 表示以第 $i$ 个位置作为当前子序列的左端点的值
状态属性
$f[i]$ 求最长上升子序列的最多景点个数
$g[i]$ 求最长下降子序列的最多景点个数
状态计算
$f[i] = max(f[i], f[j] + 1) (1 \le j < i \le n)$
$g[i] = max(g[i], g[j] + 1) (1 \le i < j \le n)$
$f$ 数组的求法和 $g$ 数组很像,因为把数组 $reverse$ 后,求新数组最长上升子序列就是求原数组最长下降子序列
答案表示
根据每一个点来划分:$ans = max$(包含 $i$ 的最长上升子序列 + 包含 $i$ 的最长下降子序列)
所以 $ans = max(f[i] + g[i] - 1)$
变量名解释:
$n$ 是景点数量
$x[]$:记录每个景点的海拔
$f[], g[]$:见上的分析
$ans$ 答案,表示最多能浏览的景点数
c++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1009;
int n, x[N]; //景点数量和景点海拔
int f[N]; //求最长上升子序列
int g[N]; //求最长下降子序列
int ans = 0;
int main()
{
cin >> n;
for(int i = 1;i <= n;++ i)
//首先求最长上升子序列
{
cin >> x[i]; f[i] = 1; //注意子序列至少有一个节点
for(int j = 1;j < i;++ j) //枚举第二个节点
if(x[i] > x[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(x[i] > x[j])
g[i] = max(g[i], g[j] + 1); //求最长下降子序列
}
for(int i = 1;i <= n;++ i)
ans = max(ans, f[i] + g[i] - 1);
cout << ans << endl;
return 0;
}
ans = max(ans, f[i] + g[i] - 1);
这个为什么-1
这个数据你看一下
5
1 4 3 2 1
因为第i个位置求了两遍,所以要
-1
for(int i=1;i<=n;i)
{
g[i] = 1;
for(int j =1;j<i;j )
{
if(a[i]<a[j])
{
g[i] = max(g[i] , g[j]+1);
}
}
}
大佬 我这个求最长下降子序列为什么不对
我也碰到了和你一样的问题!仔细想想是因为,本题要求必须从左到右浏览,所以我们只能选择一直下,或者先上后下。假设有四个数字 x1,x2,x3,x4。对于x2,我们求的是从0-x2间最长的上升子序列个数,与从x2-x4间的最长的下降子序列的个数。如果从头开始遍历,我们得到的是0-x2间的最长下降子序列个数!但实际上,我们走到x2之后是不可以再往回走的。(如果有错的话欢迎指出!)
“g[i]表示以第 i个位置作为当前子序列的右端点的值“
az,貌似是左端点吧
为什么这么求最长下降子序列不对?
rep(i,1,n){
g[i]=1;
rep(j,1,i-1){
if(a[j]>a[i])
g[i]=max(g[i],g[j]+1);
}
}
正向求最长下降子序列,g[i]表示从前往后以a[i]为结尾的最长长度。
反向求最长下降子序列,g[i]表示从后往前以a[i]为结尾的最长长度。
如果直接把正向结果与最长上升序列长度相加,得到的是从前往后以a[i]为结尾的最长上升序列长度+从前往后以a[i]为结尾的最长下降序列长度
而题目所求的可以转化为从前往后以a[i]为结尾的最长上升长度+从后往前以a[i]为结尾的最长上升长度。两者是不同的。
谢谢你,我的英雄