当前位置:网站首页>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= "<
边栏推荐
猜你喜欢
随机推荐
【Basic model】Transformer-实现中英翻译
从零开始Blazor Server(9)--修改Layout
【概率论】一元概率分布的平均化
wpf path xaml写法和c#写法对比
SQL Server查询优化
UNIX哲学
Notepad++安装插件
[工程数学]1_特征值与特征向量
Open3D 点云平均点间距评估
Open3D point cloud average point spacing evaluation
湖南进芯电子替代TIC2000的可能性
Paper Sharing | ACL2022 | Argument Relation Extraction Based on Transfer Learning
redis的缓存穿透、缓存雪崩、缓存击穿怎么搞?
JS 封装节流(后期优化)
PTA 矩阵运算
JS封装防抖(代码持续优化)
ICML 2022 | Out-of-Distribution检测与深最近的邻居
Win10调整磁盘存储空间详解
Summary of learning stages (knapsack problem)
双向链表的各种操作