#10 D. LCIS （dp+最长公共上升子序列）

#10 D. LCIS （dp+最长公共上升子序列）

题目链接：

​​i ]表示第二个串位置为 i 的时候与第一个串的的最长公共上升子序列是多少。

枚举第一个串，再枚举第二个串。

for(int i = 1; i<=n ; i++){}

AC代码：

#includeusing namespace std;int dp[567],a[567],b[567],step[567];int n,m;void print(int x){ if(x==0)return; print(step[x]); printf("%d ",b[x]);}int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } cin>>m; for(int j=1;j<=m;j++){ cin>>b[j]; } for(int i=1;i<=n;i++) { int pos=0; for(int j=1;j<=m;j++) { if(a[i]==b[j]) { dp[j]=dp[pos]+1; step[j]=pos; } else if(a[i] > b[j] && dp[j] > dp[pos]) { pos=j; } } }// for(int i=1;i<=m;i++)cout<ans) { ans=dp[i]; x=i; } } cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。