最长公共上升子序列(LCIS)
裸的算法题。
动态规划:
两组数组a[n]、b[m]。
f[i][i]表示以a[i]、b[j]结尾的两个数组的LCIS。
转移方程:
a[i]!=b[j] : f[i][j]=f[i-1][j];
a[i]==b[j] : f[i][j]=max (f[i-1][k]) + 1;(1<=k<j&&b[j]>b[k] )
max (f[i-1][k])可以在访问f[i][k]的时候维护更新一个max变量来得到,这样就是O(n*m)的时间复杂度。
ps:找这个算法的时候看到某队省赛的时候不会,同病相怜哈,还好我们只是训练赛不会。灭哈哈哈~
1 #include2 #include 3 #include 4 using namespace std; 5 6 int f[1005][1005]; 7 int main (){ //cout<<"error"< >t;13 while (t--){14 cin>>n1;15 for (int i=1;i<=n1;i++)16 cin>>a[i];17 cin>>n2;18 for (int i=1;i<=n2;i++)19 cin>>b[i];20 memset (f,0,sizeof f);21 for (int i=1;i<=n1;i++){22 max=0;23 for (int j=1;j<=n2;j++){24 f[i][j]=f[i-1][j];25 if (a[i]>b[j]&&f[i-1][j]>max)26 max=f[i-1][j];27 if (a[i]==b[j])28 f[i][j]=max+1;29 }30 }31 int ans=0;32 for (int i=1;i<=n2;i++)33 if (f[n1][i]>ans)34 ans=f[n1][i];//cout< <<" ";35 cout< <