一、题目描述
描述&＃xff1a;
N位同学站成一排&＃xff0c;音乐老师要请其中的(N-K)位同学出列&＃xff0c;使得剩下的K位同学不交换位置就能排成合唱队形。
合唱队形是指这样的一种队形&＃xff1a;设K位同学从左到右依次编号为1, 2, …, K&＃xff0c;他们的身高分别为T1, T2, …, TK&＃xff0c;则他们的身高满足T1
你的任务是&＃xff0c;已知所有N位同学的身高&＃xff0c;计算最少需要几位同学出列&＃xff0c;可以使得剩下的同学排成合唱队形。
输入&＃xff1a;
第一行整数 N&＃xff0c;表示同学的总数
第二行整数数组&＃xff0c;空格隔开&＃xff0c;表示 N 位同学身高
输出&＃xff1a;
最少需要几位同学出列
样例输入&＃xff1a;
8
186 186 150 200 160 130 197 20012
样例输出&＃xff1a;
41
二、最长递增子序列
最长递增子序列&＃xff08;Longest Increasing Subsequence&＃xff09;是指找到一个给定序列的最长子序列的长度&＃xff0c;使得子序列中的所有元素单调递增。
例如&＃xff1a;{ 3&＃xff0c;5&＃xff0c;7&＃xff0c;1&＃xff0c;2&＃xff0c;8 } 的 LIS 是 { 3&＃xff0c;5&＃xff0c;7&＃xff0c;8 }&＃xff0c;长度为 4。
解法一&＃xff1a;转化为求最长公共子序列
其实可以把 求最长递增子序列问题 转化为 求最长公共子序列的问题。
设数组 { 3&＃xff0c; 5&＃xff0c; 7&＃xff0c; 1&＃xff0c; 2&＃xff0c; 8 } 为 A
对数组 A 排序&＃xff0c;排序后的数组为 B &＃61; { 1&＃xff0c; 2&＃xff0c; 3&＃xff0c; 5&＃xff0c; 7&＃xff0c; 8 }。
于是&＃xff0c;求数组 A 的最长递增子序列&＃xff0c;就是求数组 A 与数组 B 的最长公共子序列。
最长公共子序列的求法见《动态规划DP》。本方法的时间复杂度是
Θ(nlgn)&＃43;Θ(n2)&＃61;Θ(n2)
解法二&＃xff1a;动态规划法
虽然解法一也是使用动态规划&＃xff0c;但是与解法一不同的是&＃xff0c;解法二不进行转化&＃xff0c;而是直接在原问题上采用动态规划法。
最优子结构&＃xff1a;
对于长度为 N 的数组 A[N]&＃61;{a0,a1,a2,…,an1}&＃xff0c;假设我们想求以 ai 结尾的最大递增子序列长度&＃xff0c;设为L[i]&＃xff0c;那么
L[i]&＃61;max(L[j])&＃43;1,1,where j<i and A[j]<A[i]otherwise
也就是 j 的范围是 0 到 i–1。这样&＃xff0c;想求 ai 结尾的最大递增子序列的长度&＃xff0c;我们就需要遍历 i 之前的所有位置 j&＃xff08;0到 i-1&＃xff09;&＃xff0c;找出A[j]<A[i]&＃xff0c;计算这些 j 中&＃xff0c;能产生最大 L[j] 的 j&＃xff0c;之后就可以求出 L[i]。之后对每一个A[N]中的元素都计算以他们各自结尾的最大递增子序列的长度&＃xff0c;这些长度的最大值&＃xff0c;就是我们要求的问题——数组A的最大递增子序列的长度。
重叠子问题&＃xff1a;
根据上述推导式采用递归实现的话&＃xff0c;有些子问题会被计算很多次。
动态规划法&＃xff1a;
综上所述&＃xff0c;LIS 问题具有动态规划需要的两个性质&＃xff0c;可以使用动态规划求解该问题。设数组 A &＃61; { 3&＃xff0c;5&＃xff0c;7&＃xff0c;1&＃xff0c;2&＃xff0c;8 }&＃xff0c;则&＃xff1a;
具体的打表方式如下&＃xff1a;
初始化对角线为 1&＃xff1b;
对每一个 i&＃xff0c;遍历 j&＃xff08;0 到 i-1&＃xff09;&＃xff1a;
若
A[i] <&＃61; A[j]&＃xff0c;置 1。若
A[i] > A[j]&＃xff0c;取第 j 行的最大值加 1。
打完表以后&＃xff0c;最后一行的最大值就是最长递增子序列的长度。由于每次都进行遍历&＃xff0c;故时间复杂度还是 Θ(n2) 。
通常在实现的时候我们不会创建一整个表&＃xff0c;因为这样太浪费空间。由打表的过程可知&＃xff0c;我们只需要一个一维数组来保存每一行的最大值即可&＃xff1a;
// LIS 的动态规划方式实现#include
{ /* 一维数组 */int* lis &＃61; new int[len]; /* 初始化为1 */for (int i &＃61; 0; i < len; &＃43;&＃43;i) lis[i] &＃61; 1; /* 计算每个i对应的lis最大值&＃xff0c;即打表的过程 */for (int i &＃61; 1; i < len; &＃43;&＃43;i) for (int j &＃61; 0; j < i; &＃43;&＃43;j) // 0到i-1if ( A[i] > A[j] && lis[i] < lis[j]&＃43;1)lis[i] &＃61; lis[j] &＃43; 1; // 更新/* 数组中最大的那个&＃xff0c;就是最长递增子序列的长度 */int maxlis &＃61; 0; for (int i &＃61; 0; i < len; &＃43;&＃43;i) if ( maxlis < lis[i] )maxlis &＃61; lis[i]; delete [] lis; return maxlis;
}int main()
{ int arr[] &＃61; {3, 5, 7, 1, 2, 8}; cout << getLISLength(arr, 6) << endl; return 0;
}
解法三&＃xff1a;Θ(nlgn)的方案
本解法的具体操作如下&＃xff1a;
开一个栈&＃xff0c;依次读取数组元素 x 与栈顶元素 top&＃xff1a;
如果 x > top&＃xff0c;将 x 入栈&＃xff1b;
如果 x
遍历结束之后&＃xff0c;最长递增序列长度即为栈的大小。
int getLISLength(int A[], int len) 由于使用了二分搜索&＃xff0c;故时间复杂度变成了 Θ(nlgn)。 特别注意的是&＃xff1a;本方法只能用于求最长递增子序列的长度&＃xff0c;千万不要以为栈中的序列就是最长递增子序列&＃xff1a; 例一&＃xff1a;原序列为1&＃xff0c;5&＃xff0c;8&＃xff0c;3&＃xff0c;6&＃xff0c;7 例二&＃xff1a;原序列为1&＃xff0c;5&＃xff0c;8&＃xff0c;3 根据题意可知&＃xff0c;我们需要求出一个“中间点”&＃xff0c;使得其左边的【最长递增子序列】和其右边的【最长递减子序列】之和最大。 #include 转自&＃xff1a;http://blog.csdn.net/lisonglisonglisong/article/details/45241965
{ vector
栈为1&＃xff0c;5&＃xff0c;8&＃xff0c;此时读到3&＃xff0c;用3替换5&＃xff0c;得到1&＃xff0c;3&＃xff0c;8&＃xff1b; 再读6&＃xff0c;用6替换8&＃xff0c;得到1&＃xff0c;3&＃xff0c;6&＃xff1b;再读7&＃xff0c;得到最终栈为1&＃xff0c;3&＃xff0c;6&＃xff0c;7。最长递增子序列为长度4。
则最终栈为1&＃xff0c;3&＃xff0c;8。明显这不是最长递增子序列&＃xff01;三、解题报告
using namespace std;int main()
{ int len;cin >> len; int *A &＃61; new int[len]; for(int i&＃61;0; i
京公网安备 11010802041100号