同城分类信息网站,十大企业网站排行榜,响应式网页制作工具,网站运营方案书设 A[t]表示序列中的第t个数#xff0c;F[t]表示从1到t这一段中以t结尾的最长上升子序列的长度#xff0c;初始时设F [t] 0(t 1, 2, ..., len(A))。则有动态规划方程#xff1a;F[t] max{1, F[j] 1} (j 1, 2, ..., t - 1, 且A[j] A[t])。 现在#xff0c;我们仔细…设 A[t]表示序列中的第t个数F[t]表示从1到t这一段中以t结尾的最长上升子序列的长度初始时设F [t] 0(t 1, 2, ..., len(A))。则有动态规划方程F[t] max{1, F[j] 1} (j 1, 2, ..., t - 1, 且A[j] A[t])。 现在我们仔细考虑计算F[t]时的情况。假设有两个元素A[x]和A[y]满足 (1)x y t (2)A[x] A[y] A[t] (3)F[x] F[y] 此时选择F[x]和选择F[y]都可以得到同样的F[t]值那么在最长上升子序列的这个位置中应该选择A[x]还是应该选择A[y]呢 很明显选择A[x]比选择A[y]要好。因为由于条件(2)在A[x1] ... A[t-1]这一段中如果存在A[z]A[x] A[z] a[y]则与选择A[y]相比将会得到更长的上升子序列。 再根据条件(3)我们会得到一个启示根据F[]的值进行分类。对于F[]的每一个取值k我们只需要保留满足F[t] k的所有A[t]中的最小值。设D[k]记录这个值即D[k] min{A[t]} (F[t] k)。 注意到D[]的两个特点 (1) D[k]的值是在整个计算过程中是单调不下降的。 (2) D[]的值是有序的即D[1] D[2] D[3] ... D[n]。 利 用D[]我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A[t]与D[len]。若A [t] D[len]则将A[t]接在D[len]后将得到一个更长的上升子序列len len 1 D[len] A [t]否则在D[1]..D[len]中找到最大的j满足D[j] A[t]。令k j 1则有A [t] D[k]将A[t]接在D[j]后将得到一个更长的上升子序列更新D[k] A[t]。最后len即为所要求的最长上 升子序列的长度。 在 上述算法中若使用朴素的顺序查找在D[1]..D[len]查找由于共有O(n)个元素需要计算每次计算时的复杂度是O(n)则整个算法的 时间复杂度为O(n^2)与原来的算法相比没有任何进步。但是由于D[]的特点(2)我们在D[]中查找时可以使用二分查找高效地完成则整个算法 的时间复杂度下降为O(nlogn)有了非常显著的提高。需要注意的是D[]在算法结束后记录的并不是一个符合题意的最长上升子序列 1 #includecstdio2 #includecstring3 #includealgorithm4 #includeiostream5 using namespace std;6 7 const int mx100005;8 int a[mx],d[mx];9
10 int BinSerch(int l,int r,int cut)
11 {
12 while (lr)
13 {
14 int m(lr)1;
15 if (cutd[m]cutd[m1]) return m;
16 if (cutd[m]) lm1;
17 else rm-1;
18 }
19 return 0;
20 }
21
22 int LIS(int n)
23 {
24 int len1,j;
25 d[1]a[0];
26 for (int i1;in;i)
27 {
28 if (a[i]d[len]) jlen;
29 else jBinSerch(1,len,a[i])1;
30 d[j]a[i];
31 }
32 return len;
33 }
34
35 int main()
36 {
37 int n;
38 while (~scanf(%d,n))
39 {
40 for (int i0;in;i) scanf(%d,a[i]);
41 printf(%d\n,LIS(n));
42 }
43 } 转载于:https://www.cnblogs.com/pblr/p/5718875.html
