問題 F: 【動態規劃】最長公共上升子序列

時間限制: 5 Sec??內存限制: 64 MB
提交: 34??解決: 9
[提交] [狀態] [命題人:admin]

題目描述

研究發現，大猩猩的基因序列和人的基因序列只有1.3%的區別，更進一步，不僅僅離人最近的大猩猩和人的基因序列高度近似，就連以打洞為生的老鼠和人的基因序列也有高達95%的相同序列。于是有魔法師提出一個大膽設想，即改變人類的某些特定基因以期產生超級人類。

??? 現在，他們要做的第一步是將兩種不同生物的基因序列轉換成兩個整數序列，并試圖確定他們的最大公共上升子序列的長度，例如有A序列為4 3 2 1 7 8 9，B序列為7 8 9 4 3 2 1，其最長公共子序列是4 3 2 1，而最長公共遞增子序列應該是 7 8 9。

?

輸入

輸入每個序列由M個整數組成(1 ≤ M ≤500)，M個整數范圍在(－2³¹ ≤Bi < 2³¹)之間。

?

輸出

輸出最長公共上升子序列長度L。

?

樣例輸入

復制樣例數據

5 1 4 2 5 -12 4 -12 1 2 4

樣例輸出

2
#include <bits/stdc++.h> #include<map> #include<set> using namespace std; const int maxn=666; typedef long long ll; int n,m; ll p[maxn],q[maxn],ans,dp[maxn][maxn]; int main() {cin>>n;for(int i=1;i<=n;i++)scanf("%lld",&p[i]);cin>>m;for(int i=1;i<=m;i++)scanf("%lld",&q[i]);for(int i=1;i<=n;i++){ll cur=0;for(int j=1;j<=m;j++){dp[i][j]=dp[i-1][j];if(p[i]>q[j]&&dp[i-1][j]>cur)cur=dp[i-1][j];if(p[i]==q[j])dp[i][j]=cur+1;}}for(int i=1;i<=m;i++)ans=max(ans,dp[n][i]);cout<<ans<<endl;return 0; }

?

轉載于:https://www.cnblogs.com/czy-power/p/10616269.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的【动态规划】最长公共上升子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。