当前位置:网站首页>ACM longest non-descent subsequence problem
ACM longest non-descent subsequence problem
2022-08-09 11:44:00 【catch a ponytail girl】
Given a string of numbers, find its longest non-descending subsequence
This problem is a classic dp linear problem, define a three-dimensional array, a[i][1] represents the value, a[i][2] represents the length of the longest subsequence from i to n, and a[i][3] represents the position of the number following the i subsequence.
#includeusing namespace std;int a[100][10],k,l;int main(){int n;cin>>n;for(int i=1;i<=n;i=i+1){cin>>a[i][1];a[i][2]=1;a[i][3]=0;}for(int i=n-1;i>=1;i=i-1){k=0;l=0;for(int j=i+1;j<=n;j=j+1)if((a[j][1]>a[i][1])&&a[j][2]>l){k=j;l=a[j][2];}if(l>0){a[i][2]=l+1;a[i][3]=k;}}k=1;for(int i=1;i<=n;i=i+1)if(a[i][2]>a[k][2])k=i;cout<<"max= "<
边栏推荐
猜你喜欢
随机推荐
CANopen DS402名词
排序--快排(图解)
Oracle数据库的两种进入方式
JS 封装节流(后期优化)
enum in c language
人体解析(Human Parse)开源数据集整理
The use of signal function (signal) in C language
ACM最长不下降子序列问题
es6递归函数
PTA习题 三角形判断
PAT 1015 进制转换
JS封装防抖(代码持续优化)
PAT1006
[现代控制理论]3_Phase_portrait 相图 相轨迹
PAT1008
【精华文】C语言结构体特殊情况分析:结构体指针 / 基本数据类型指针,指向其他结构体
元宇宙:下一代互联网启程(附元宇宙深度报告PDF)
ZOJ 1729 & ZOJ 2006(最小表示法模板题)
LeetCode_单调栈_中等_456.132 模式
电解电容漏电流及均压