Description

Input

Output

Sample Input

5
1 4 2 5 1
4
1 1 2 4

Sample Output

2
1 4

Data Constraint

Solution

• 考慮 DP。設狀態(tài) F[i][j] 表示 a 序列考慮到 i, b 序列考慮到 j 并且必須選 bj 的最大長度。

• 當 ai=bj 時, 顯然有轉(zhuǎn)移：

  F[i][j]=Maxk<j,bk<bjF[i?1][k]+1。

• 于是從小到大枚舉 j , 維護 Maxk<j,bk<aif[i?1][k] 。

• 又發(fā)現(xiàn)其實第一位狀態(tài)并沒有什么用，

• 狀態(tài)可以設為 F[i] 表示 b 序列考慮到 j 并且必須選 bj 的最大長度。

• 這樣的轉(zhuǎn)移就十分顯然而簡易了。

• 那么如何統(tǒng)計答案呢？每當 F 值被更新時就用一個鏈表存儲當前點從哪里轉(zhuǎn)移過來。

• 那么最后找到最優(yōu)的答案 F[k] ，從這個 k<script type="math/tex" id="MathJax-Element-2063">k</script> 點沿著鏈表一直往前就是方案了。

Code

#include<cstdio> #include<vector> using namespace std; const int N=5001; int ans,tot; vector<int>next,en; int a[N],b[N],f[N],first[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } int main() {int n=read();for(int i=1;i<=n;i++) a[i]=read();int m=read();for(int i=1;i<=m;i++) b[i]=read();next.push_back(0);en.push_back(0);for(int i=1;i<=n;i++)for(int j=1,k=0,p=0;j<=m;j++)if(a[i]==b[j]){if(f[k]+1>f[j]){f[j]=f[k]+1;first[j]=++tot;next.push_back(p);en.push_back(j);}}elseif(a[i]>b[j] && f[j]>f[k]) p=first[k=j];for(int i=1;i<=n;i++)if(f[i]>f[ans]) ans=i;printf("%d\n",f[ans]);for(int i=first[ans];i;i=next[i]) f[++f[0]]=en[i];for(int i=f[0];i;i--) printf("%d ",b[f[i]]);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5424. 【NOIP2017提高A组集训10.25】凤凰院凶真的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。