【CF10D】LCIS（LCIS）

题意：求两个序列的LCIS

n,m<=300，a[i]<=1e9

题意：O(n^2)

O(n^3)的话设dp[i,j]为A终点为a【1..i】且B终点为b[j]的最大长度，分a[i]==b[j]和a[i]!=b[j]转移，枚举前一个在b中取的位置k转移

发现转移的下标集合每次只扩大最后一个，用前缀max保存

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef unsigned int uint;
 5 typedef unsigned long long ull;
 6 typedef long double ld;
 7 typedef pair<int,int> PII;
 8 typedef pair<ll,ll> Pll;
 9 typedef vector<int> VI;
10 typedef vector<PII> VII;
11 typedef pair<ll,ll>P;
12 #define N  510
13 #define M  1000000
14 #define INF 1e9
15 #define fi first
16 #define se second
17 #define MP make_pair
18 #define pb push_back
19 #define pi acos(-1)
20 #define mem(a,b) memset(a,b,sizeof(a))
21 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
22 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
23 #define lowbit(x) x&(-x)
24 #define Rand (rand()*(1<<16)+rand())
25 #define id(x) ((x)<=B?(x):m-n/(x)+1)
26 #define ls p<<1
27 #define rs p<<1|1
28 #define fors(i) for(auto i:e[x]) if(i!=p)
29 
30 const int MOD=1e9+7,inv2=(MOD+1)/2;
31       double eps=1e-6;
32       int dx[4]={-1,1,0,0};
33       int dy[4]={0,0,-1,1};
34 
35 int dp[N][N],pre[N][N],a[N],b[N],c[N];
36 
37 int read()
38 {
39    int v=0,f=1;
40    char c=getchar();
41    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
42    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
43    return v*f;
44 }
45 
46 int main()
47 {
48     int n=read();
49     rep(i,1,n) a[i]=read();
50     int m=read();
51     rep(i,1,m) b[i]=read();
52     rep(i,1,n)
53     {
54         int mx=0,y=0;
55         rep(j,1,m)
56         {
57             dp[i][j]=pre[i][j]=0;
58             if(a[i]!=b[j])
59             {
60                 dp[i][j]=dp[i-1][j];
61                 pre[i][j]=j;
62             }
63             if(a[i]>b[j]&&mx<dp[i-1][j])
64             {
65                 mx=dp[i-1][j];
66                 y=j;
67             }
68             if(a[i]==b[j])
69             {
70                 dp[i][j]=mx+1;
71                 pre[i][j]=y;
72             }
73         }
74     }
75     int x=n,y,ans=0;
76     rep(i,1,m)
77      if(dp[n][i]>ans)
78      {
79          ans=dp[n][i];
80          y=i;
81      }
82     printf("%d
",ans);
83     if(ans==0) return 0;
84     int t=0;
85     while(x)
86     {
87         if(a[x]==b[y]) c[++t]=b[y];
88         y=pre[x][y];
89         x--;
90     }
91     per(i,ans,1) printf("%d ",c[i]);
92     return 0;
93 }