当前位置:网站首页>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= "<
边栏推荐
猜你喜欢
bat文件(批处理文件)运行时一闪而过解决方法
Semaphore SIGCHLD use, how to make the parent that the child performs over, how to make the distinction between multiple child processes. The end
爱可可AI前沿推介(8.9)
wpf实现简易画板功能(带截取画板,签名截图等等)
2022 全球 AI 模型周报
抗积分饱和 PID代码实现,matlab仿真实现
[现代控制理论]4_PhasePortrait爱情故事动态系统分析
Win10调整磁盘存储空间详解
x86 exception handling and interrupt mechanism (2) interrupt vector table
链表基本操作(详解)
随机推荐
学长告诉我,大厂MySQL都是通过SSH连接的
Redis高可用部署
《数字经济全景白皮书》银行业智能营销应用专题分析 发布
[现代控制理论]2_state-space状态空间方程
ZOJ1298(单源最短路径)
字符串 | 反转字符串 | 双指针法 | leecode刷题笔记
WPF 实现带蒙版的 MessageBox 消息提示框
buck型三相PFC
PTA 矩阵运算
[现代控制理论]6_稳定性_李雅普诺夫_Lyapunov
【VQA survey】视觉问答中的语言学问题
Oracle数据库体系结构
mysql8.0和navicat premium15下载安装
Redis的常用数据结构和底层实现方式
wpf实现简易画板功能(带截取画板,签名截图等等)
OC-NSTimer
PAT 1015 进制转换
PAT1009
ClickHouse物化视图(八)
PAT1007