当前位置:网站首页>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= "<
原网站

版权声明
本文为[catch a ponytail girl]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/221/202208091102024527.html