最长上升子序列问题

题目：1014. 登山

思路

First

这题也可以看作最长上升子序列，只不过这个序列有三种情况。

先上升，后下降
先上升，不下降
不上升，直接下降

其实这三种情况我们可以归纳为一种情况：先上升后下降。先上升不下降的可以看成”先上升后下降为零“；不上升直接下降可以看成”先上升零后下降“

我们可以参考直接的母题模板。

定义：f[i]表示以该点为中的终点的最长上升子序列的最大长度，a[i]表示以该点为起点的最长下降子序列（终点是整个序列的最后一个元素）
运用之前的模板，把以每一个点为终点的最长上升子序列最大长度和以其为起点的最长下降子序列最大长度求解处理（即f[]a[]求解）
遍历循环每一个点，我们将该点作为上升和下降的转折点（在该点之前上升，在该点之后下降），即a[i]+f[i],然后我们求出最大的那个即为答案。注意，由于这个点被加了两次，所以最后要减去一次。

Second

上面的那种思路非常好想到，这题还有一种思路。

我们可以利用状态机模型DP解决最长xxx子序列模型的方法（这个状态机模型我也不是很清楚，是在题解上看到大佬写的，等以后刷的题多了应该会了解的）。

xxx可以是先上升后下降，或者先上升后下降再上升，或者先上升后下降再上升再下降 ···

对于本题来说，如果当前状态是上升，那么它的下一阶段可以维持上升状态，也可以变成下降状态；而如果当前状态是下降状态，那么它下一阶段就只能维持下降状态。

定义：f[i][k]表示以i为终点，当前状态是k最大方案子序列长度。
初始状态：f[0][0]和f[0][1]，目标状态：f[n-1][0]和f[n-1][1]
状态转移：遍历循环每一个点，对于每一个节点i，我们接着枚举每一个在i前面的节点j，这样有两种情况(由于题目说明了不浏览海拔相等的，所以就不考虑相等的情况)：

如果p[j]<p[i],那么节点i只能由节点j的上升状态转移而来。
如果P[j]<p[i],那么节点i既可以由节点j的上升状态转移而来也可以由j的下降状态转移而来。

最后，我们只需要比较每一个节点的f[i][0]和f[i][1]，找到最大的即是答案。

代码

First

#include<iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int n;
	cin >> n;
	int p[1010], f[1010], a[1010];
	for (int i = 1; i <= n; i++)
	{
		f[i] = 1;
		a[i] = 1;
		cin >> p[i];
	}

	int res = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < i; j++)
			if (p[i] > p[j])
				f[i] = max(f[i], f[j] + 1);
	}
	
	for (int i = n; i > 0; i--)
		for (int j = n; j > i; j--)
			if (p[i] > p[j])
				a[i] = max(a[i], a[j] + 1);
	
	for (int i = 1; i <= n; i++)
		res = max(res, f[i] + a[i]-1);

	cout << res << endl;
}

Second

#include<iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int n, p[1010], f[1010][2];
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		f[i][0] = f[i][1] = 1;
		cin >> p[i];
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < i; j++)
		{
			if (p[j] < p[i])
				f[i][0] = max(f[i][0], f[j][0] + 1);
			if (p[j] > p[i])
				f[i][1] = max(f[i][1], max(f[j][0], f[j][1]) + 1);
		}
	}

	int res = 1;
	for (int i = 1; i <= n; i++)
		res = max(max(f[i][1], f[i][0]), res);
	cout << res << endl;
}

题目：482. 合唱队形

思路：

和上一题一模一样

代码

#include<iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int n, p[1010], f[1010][2];
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		f[i][0] = f[i][1] = 1;
		cin >> p[i];
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < i; j++)
		{
			if (p[j] < p[i])
				f[i][0] = max(f[i][0], f[j][0] + 1);
			if (p[j] > p[i])
				f[i][1] = max(f[i][1], max(f[j][0], f[j][1]) + 1);
		}
	}

	int res = 1;
	for (int i = 1; i <= n; i++)
		res = max(max(f[i][1], f[i][0]), res);
	cout << n - res << endl;
}

#include<iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int n;
	cin >> n;
	int p[1010], f[1010], a[1010];
	for (int i = 1; i <= n; i++)
	{
		f[i] = 1;
		a[i] = 1;
		cin >> p[i];
	}

	int res = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < i; j++)
			if (p[i] > p[j])
				f[i] = max(f[i], f[j] + 1);
	}

	for (int i = n; i > 0; i--)
		for (int j = n; j > i; j--)
			if (p[i] > p[j])
				a[i] = max(a[i], a[j] + 1);

	for (int i = 1; i <= n; i++)
		res = max(res, f[i] + a[i] - 1);

	cout << n - res << endl;
}

写在最后

个人亲身经验：我们学习的一系列Linux命令，一定要自己亲手去敲。不要只是看别人敲代码，不要只是停留在眼睛看，脑袋以为自己懂了，等你实际上手去敲会发现许许多多的这样那样的问题。毕竟“实践出真知”。

如果你觉得我写的题解还不错的，请各位王子公主移步到我的其他题解看看

数据结构与算法部分（还在更新中）：

C++ STL总结 - 基于算法竞赛（强力推荐）
动态规划——01背包问题
动态规划——完全背包问题
动态规划——多重背包问题
动态规划——分组背包问题
动态规划——最长上升子序列（LIS)
二叉树的中序遍历（三种方法）
最长回文子串
最短路算法——Dijkstra（C++实现）
最短路算法———Bellman_Ford算法（C++实现）
最短路算法———SPFA算法（C++实现）
最小生成树算法———prim算法（C++实现）
最小生成树算法———Kruskal算法（C++实现）
染色法判断二分图（C++实现）

Linux部分（还在更新中）：

Linux学习之初识Linux
Linux学习之命令行基础操作
Linux学习之基础命令（适合小白）
Linux学习之权限管理和用户管理
Linux学习之制作静态库和动态库
Linux学习之makefile
Linux学习之系统编程1（关于读写系统函数）
Linux学习之系统编程2（关于进程及其相关的函数）
Linux学习之系统编程3（进程及wait函数）
Linux学习之系统编程4(进程间通信）
Linux学习之系统编程5(信号）
Linux学习之系统编程6(线程）
Linux学习之系统编程7(线程同步/互斥锁/信号量/条件变量）
Linux学习之网络编程（纯理论）
Linux学习之网络编程2（socket，简单C/S模型）