B3637 最长上升子序列

最长上升子序列

题目描述

这是一个简单的动规板子题。

给出一个由 $n(n\le 5000)$ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数 $n$，表示序列长度。

第二行有 $n$ 个整数，表示这个序列。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

6
1 2 4 1 3 4

样例输出 #1

4

提示

分别取出 $1$、$2$、$3$、$4$ 即可。

题意

给出一个由 $n(n\le 5000)$ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

正解

动态规划（DP）。

动态规划分为三部分：

一、确定状态：确定 dp 数组里装的是什么，像这道题要求最长上升子序列的长度，$d{p}_i$ 存的就是 $a_1,a_2,\dots ,a_i$ 的最长上升子序列的长度。

二、确定转移公式：dp 的思想就是从以前的答案转移过来，所以要确定转移公式。如果 $a_j<a_i(j<i)$，那么 $a_i,a_j$ 就是一个上升子序列，那么 $d{p}_i=d{p}_j+1$，所以转移公式就是：

for (int j = 1;j < i;j++)
	if (a[j] < a[i])
		dp[i] = max(dp[i],dp[j]+1);

但是如果 $a_i$ 前面的数都比它大，那么 $d{p}_i$ 就得设置一个初始值 $1$。也就是：

for (int i = 1;i <= n;i++)
{
	dp[i] = 1;
	for (int j = 1;j < i;j++)
		if (a[j] < a[i])
			dp[i] = max(dp[i],dp[j]+1);
}

三、确定最后的答案：在这里，最后的答案应该是 $\max (d{p}_1,d{p}_2,\dots ,d{p}_n)$。也就是：

int mx = 0;
for (int i = 1;i <= n;i++)
	mx = max(mx,dp[i]);
cout << mx;

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,a[5010];
int dp[5010];

void solve()
{
	cin >> n;
	for (int i = 1;i <= n;i++)
		cin >> a[i];
	for (int i = 1;i <= n;i++)
	{
		dp[i] = 1;
		for (int j = 1;j < i;j++)
			if (a[j] < a[i])
				dp[i] = max(dp[i],dp[j]+1);
	}
	int mx = 0;
	for (int i = 1;i <= n;i++)
		mx = max(mx,dp[i]);
	cout << mx;
}

signed main()
{
	solve();
	return 0;
}