ZJU2136 Longest Ordered Subsequence

本文主要是介绍ZJU2136 Longest Ordered Subsequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这是一道经典的最长上升子序列问题，首先确定阶段和状态。然而每个阶段仅仅有一个状态，使用一位数组递推。
令 dp[i] 表示以 i 结尾的最长上升子序列的长度，则有

dp[i] = { max(dp[j]) + 1 | 0 <= j <i, seq[i] > seq[j] }

边界 dp[0] = 1 表示首个为结尾的最长串长度为1。

#define LOCAL
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;const int maxn = 1005;int main() {
#ifdef LOCALfreopen("input.txt", "r", stdin);
#endifint seq[maxn], dp[maxn], i, j;int kase; cin >> kase;while (kase--) {int N; cin >> N;for (i = 0; i < N; ++i) cin >> seq[i];memset(dp, 0, sizeof(dp));dp[0] = 1;for (i = 1; i < N; ++i) {dp[i] = 1;for (j = 0; j < i; ++j) {if (seq[j] < seq[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;}}int maxnum = 0;for (i = 0; i < N; ++i) {if (dp[i] > maxnum)maxnum = dp[i];}cout << maxnum << endl;if (kase != 0) cout << endl;}return 0;
}

分析如下代码片段：

        for (i = 1; i < N; ++i) {dp[i] = 1;for (j = 0; j < i; ++j) {if (seq[j] < seq[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;}}

第一个 for 循环从 1 到 N-1，计算从第二个到最后一个数字结尾的最长递增串长度，对应于转移方程中的 max(dp[j])，即遍历找到 dp 数组中 i 前面最大的且数字要小于 i 的，然后 +1。对应于 dp[i] = dp[j] + 1，已经讲得很明白了

这篇关于ZJU2136 Longest Ordered Subsequence的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---