淘宝单网站建设,微信怎么做链接网站,wordpress 添加幻灯片,网站换vps文章目录题目描述样例解析仔细审题#xff01;#xff01;#xff01;#xff01;代码题目描述
给定一个序列 求出它的单调上升序列长度并输出这个序列
样例
in:
13 7 9 16 38 24 37 18 44 19 21 22 63 15
out#xff1a;
max8
7 9 16 18 19 21 22 63解析
这题我一开始…
文章目录题目描述样例解析仔细审题代码题目描述
给定一个序列 求出它的单调上升序列长度并输出这个序列
样例
in:
13 7 9 16 38 24 37 18 44 19 21 22 63 15
out
max8
7 9 16 18 19 21 22 63解析
这题我一开始看成了有一个n。。。 调了一百多年 这题出的不好
仔细审题
因为要输出最终序列 所以各种nlogn的写法似乎都不太奏效了。。。 不过好在这题n^2的算法也能过 对于每一位转移方程为
for(int j1;ji;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]);
}代码
#includebits/stdc.h
#define ll long long
using namespace std;
const int N1e5100;
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 i1;in;i){dp[i]1;last[i]0;for(int j1;ji;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],tot0;for(int i1;in;i){if(totdp[i]){totdp[i];idi;
// 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
*/
