文章目录

• 题目描述
• • • 样例
• 解析
• • • 仔细审题！！！！
• 代码

题目描述

给定一个序列
求出它的单调上升序列长度并输出这个序列

样例

in: 13 7 9 16 38 24 37 18 44 19 21 22 63 15 out： max=8 7 9 16 18 19 21 22 63

解析

这题我一开始看成了有一个n。。。
调了一百多年
这题出的不好

仔细审题！！！！

因为要输出最终序列
所以各种nlogn的写法似乎都不太奏效了。。。
不过好在这题n^2的算法也能过
对于每一位，转移方程为：

for(int j=1;j<i;j++){if(a[i]>a[j]){if(dp[i]<dp[j]+1){dp[i]=dp[j]+1;last[i]=j;}} }

其中last数组类似于链式前向星的做法；
qytdl提供了一种递归输出结果的方法我觉得还是很妙的

void print(int x){if(!x) return;print(last[x]);printf("%d ",a[x]); }

代码

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+100; ll a[N],dp[N],last[N]; int n; void print(int x){if(!x) return;print(last[x]);printf("%d ",a[x]); } int main(){while(scanf("%d",&a[++n])!=EOF);n--;for(int i=1;i<=n;i++){dp[i]=1;last[i]=0;for(int j=1;j<i;j++){if(a[i]>a[j]){if(dp[i]<dp[j]+1){dp[i]=dp[j]+1;last[i]=j;}}} // printf("i=%d dp=%d\n",i,dp[i]);}ll id,ans[N],tot=0;for(int i=1;i<=n;i++){if(tot<dp[i]){tot=dp[i];id=i; // printf("tot=%d,i=%d\n",tot,i);}}printf("max=%d\n",tot);print(id);return 0; } /* 14 13 7 9 16 38 24 37 18 44 19 21 22 63 15 */

总结

以上是生活随笔为你收集整理的不止代码：最长上升序列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。