【CSP模拟赛】凤凰院凶真（最长公共上升子序列）

题目描述

  α世界线.凤凰院凶真创立了反抗SERN统治的组织“瓦尔基里”.为了脱离α线,他需要制作一个世界线变动率测量仪.

  测量一个世界线相对于另一个世界线的变动率,实质上就是要求出这两个世界线的最长公共合法事件序列.

  一个世界线的事件逻辑序列是一个正整数序列,第k个数表示第k个事件发生的时间.对于一个世界线,一个合法的事件序列是事件逻辑序列的一个子序列,满足时间严格递增.

  现在,对于两个不同的世间线α,β求出最长的一个事件序列,满足这个序列在α，β世界线中均是合法的.这个序列也就是之前提到过的最长公共合法事件序列.

输入描述

  第一行一个整数n,表示世界线α的事件个数.

  第二行n个整数a1;a2......an,表示世界线的事件逻辑序列.

  第三行一个整数m,表示世界线β的事件个数.

  第四行m个整数b1;b2......bm,表示世界线的事件逻辑序列.

输出描述

  第一行一个整数k,表示最长公共合法事件序列的长度.

  第二行k个整数,表示最长公共合法事件序列.如果有多解,输出任意一个.

样例输入

  5
  1 4 2 5 1
  4
  1 1 2 4

样例输出

  2

  1 4

分析

  虽然听机房的大佬们说这是一道最长公共上升子序列的板子题，然而我不会。。。。。。

  根据最长公共序列的求法，可以考虑二维状态dp[i][j]

  如果dp[i][j]表示a序列前i个事件，b序列前j个事件构成的最长公共上升子序列的长度，转移时因为不知道最后一项的大小所以无法转移

  如果dp[i][j]表示a序列第i个事件，b序列第j个事件作为结尾的