国外网站设计公司,如何设计培训课程网页,网站建设的入门书籍,火星时代教育培训机构怎么样题目链接#xff1a;http://codevs.cn/problem/1576/题目描述 Description给一个数组a1, a2 ... an#xff0c;找到最长的上升降子序列ab1ab2 .. abk#xff0c;其中b1b2..bk。 输出长度即可。 输入描述 Input Description第一行#xff0c;一个整数N。… 题目链接http://codevs.cn/problem/1576/ 题目描述 Description 给一个数组a1, a2 ... an找到最长的上升降子序列ab1ab2 .. abk其中b1b2..bk。 输出长度即可。 输入描述 Input Description 第一行一个整数N。 第二行 N个整数N 5000 输出描述 Output Description 输出K的极大值即最长不下降子序列的长度 样例输入 Sample Input 5 9 3 6 2 7 样例输出 Sample Output 3 数据范围及提示 Data Size Hint 【样例解释】 最长不下降子序列为3,6,7 解题思路 参考北大郭炜老师 1.找子问题“求以ak k1, 2, 3…N为终点的最长上升子序列的长度”一个上升子序列中最右边的那个数称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样但是只要这N个子问题都解决了那么这N个子问题的解中最大的那个就是整个问题的解。 2. 确定状态子问题只和一个变量-- 数字的位置相关。因此序列中数的位置k 就是“状态”而状态 k 对应的“值”就是以a[k]做为“终点”的最长上升子序列的长度。状态一共有N个。 3. 找出状态转移方程 maxLen [k]表示以a[k]做为“终点”的最长上升子序列的长度那么初始状态 maxLen [1] 1maxLen[k] max { maxLen [i] 1i k 且 a[i ] a[k]且 k≠1 } 1若找不到这样的i,则maxLen[k] 1 maxLen[k]的值就是在a[k]左边“终点”数值小于a[k] 且长度最大的那个上升子序列的长度再加1。因为a[k]左边任何“终点”小于a[k]的子序列加上a[k]后就能形成一个更长的上升子序列 。 1 #include stdio.h2 #define maxN 50053 int n,a[maxN],maxLen[maxN];//maxLen[k]表示以a[k]做为“终点”的最长上升子序列的长度4 int main(int argc, char *argv[])5 {6 int i,j;7 scanf(%d,n);8 for(i0;in;i) { scanf(%d,a[i]); maxLen[i]1; }9
10 for(i1;in;i)//枚举所有子序列的终点
11 {
12 for(j0;ji;j)//枚举以a[i]做终点的子序列中a[i]的前缀元素
13 {
14 if(a[j]a[i])//尝试用a[j]做a[i]的直接前缀形成新的子序列
15 {
16 maxLen[i](maxLen[j]1maxLen[i]?maxLen[j]1:maxLen[i]);
17 }
18 }
19 }
20 printf(%d\n,maxLen[n-1]);
21 return 0;
22 } 上面的代码写错了抱歉。更正如下 1 #include stdio.h2 #define maxN 50053 int main(int argc, char *argv[])4 {5 int i,j,t;6 int n,a[maxN],maxLen[maxN];//maxLen[k]表示以a[k]做为“终点”的最长上升子序列的长度7 int max;8 9 scanf(%d,n);
10 for(i0;in;i) { scanf(%d,a[i]); maxLen[i]1; }
11 for(i1;in;i)//枚举所有子序列的终点
12 {
13 for(j0;ji;j)//枚举以a[i]做终点的子序列中a[i]的前缀元素
14 {
15 if(a[j]a[i])//尝试用a[j]做a[i]的直接前缀形成新的子序列
16 {
17 maxLen[i](maxLen[j]1maxLen[i]?maxLen[j]1:maxLen[i]);
18 }
19 }
20 }
21 maxmaxLen[0];
22 for(i1;in;i)
23 if(maxLen[i]max) maxmaxLen[i];
24 printf(%d\n,max);
25 return 0;
26 } 思考题 如何改进程序使之能够输出最长上升子序列 思路新增pre[ ]其中pre[k]x表示在a[ ]序列构成的若干个上升子序列中a[k]的前驱是a[x]。一开始pre[ ]全部初始化为-1表示一开始所有元素的前驱都是自己本身。在循环求解maxLen[i]的同时更新pre[i]。最后在扫描出maxLen[ ]最大值为maxLen[i]以后从pre[i]往前推即可。假如要顺序输出该最长上升子序列可以把逆推pre[ ]的过程保存再输出。 参考代码 1 #includestdio.h2 #includestring.h3 #define maxN 50054 int main(int argc, char *argv[])5 {6 int i,j,t;7 int n,a[maxN],maxLen[maxN];//maxLen[k]表示以a[k]做为“终点”的最长上升子序列的长度8 int max;9 int pre[maxN];
10 int c[maxN],maxIndex;
11
12 memset(pre,-1,sizeof(pre));
13
14 scanf(%d,n);
15 for(i0;in;i) { scanf(%d,a[i]); maxLen[i]1; }
16
17 for(i1;in;i)//枚举所有子序列的终点
18 {
19 for(j0;ji;j)//枚举以a[i]做终点的子序列中a[i]的前缀元素
20 {
21 if(a[j]a[i])//尝试用a[j]做a[i]的直接前缀形成新的子序列
22 {
23 if(maxLen[j]1maxLen[i])
24 {
25 maxLen[i]maxLen[j]1;
26 pre[i]j;
27 }
28 }
29 }
30 }
31 maxmaxLen[0];
32 for(i1;in;i)
33 if(maxLen[i]max) { maxmaxLen[i]; maxIndexi; }
34 printf(%d\n,max);
35
36 j0;
37 c[j]a[maxIndex];
38 while(pre[maxIndex]!-1)
39 {
40 maxIndexpre[maxIndex];
41 c[j]a[maxIndex];
42 }
43 for(ij-1;i0;i--)
44 {
45 printf(%d ,c[i]);
46 }
47 printf(\n);
48 return 0;
49 } View Code 输出最长上升子序列的另一种思路 1 #include stdio.h2 int n,size,a[1005][5],s,ans,next;3 int main(int argc, char *argv[])4 {5 scanf(%d,n);6 for(int i0;in;i)7 {8 int t;9 scanf(%d,t);
10 a[i][0]t;a[i][1]1;a[i][2]0;
11 //a[i][1]表示以a[i][0]开头的最长上升子序列的长度。
12 //a[i][2]表示在以a[i][0]开头的最长上升子序列中a[i][0]的下一个数在原序列中的下标。
13 }
14
15 for(int in-2;i0;i--)
16 {
17 sizenext0;
18 for(int ji1;jn;j)
19 if(a[j][0]a[i][0]a[j][1]size) {sizea[j][1];nextj;}
20 if(size0) {a[i][1]size1;a[i][2]next;}
21 }
22
23 ans0;
24 for(int i0;in;i)
25 if(a[i][1]a[ans][1]) ansi;
26
27 printf(%d\n,a[ans][1]);
28
29 /*for(int i0;in;i)
30 printf(%d %d %d %d\n,a[i][0],a[i][1],a[i][2],i);*/
31
32 int ians;
33 while(a[i][2]0)
34 {
35 printf(%d ,a[i][0]);
36 ia[i][2];
37 }
38 printf(%d\n,a[i][0]);
39 return 0;
40 } View Code 测试OJ地址 http://noi.openjudge.cn/ch0206/1759/ http://bailian.openjudge.cn/practice/2757/ 转载于:https://www.cnblogs.com/huashanqingzhu/p/7326739.html
