正題

題目鏈接:http://www.joyoi.cn/problem/tyvj-1071

---

題目大意

求兩個序列的最長公共上升子序列。

---

code

我們先回顧一下LIS和LCS
LIS:

fi=max{fj+1}(j<i,aj<ai)fi=max{fj+1}(j<i,aj<ai)
我們將其融合一下就變成了
fi,j=max{fi?1,k}+1(k<j,bk<ai)fi,j=max{fi?1,k}+1(k<j,bk<ai) 的算法就出來了。

---

code

#include<cstdio> #include<algorithm> using namespace std; int n,m,a[3001],b[3001],f[3001][3001],val; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++) { val=0;//統計答案的變量 for(int j=1;j<=n;j++) { if(a[i]==b[j]) f[i][j]=val+1; else f[i][j]=f[i-1][j];//動態轉移 if(b[j]<a[i]) val=max(val,f[i-1][j]);//更新最大值 } } val=0; for(int i=1;i<=n;i++) val=max(val,f[n][i]); printf("%d",val); }

總結

以上是生活随笔為你收集整理的JoyOI(TYVJ)1071-LCIS【线性dp,LIS,LCS】的全部內容，希望文章能夠幫你解決所遇到的問題。

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