玄关求条
  • 板块CF10D LCIS
  • 楼主Terry_RE
  • 当前回复7
  • 已保存回复7
  • 发布时间2025/7/21 17:03
  • 上次更新2025/7/21 22:26:05
查看原帖
玄关求条
1007305
Terry_RE楼主2025/7/21 17:03
#include<bits/stdc++.h>
using namespace std;

const int N = 3030;

int a[N];
int b[N];

int dp[N];

int path[N];

int n, m;

int ans;

int ans1[N];

int pos;

int main(){
    cin.tie(0) -> ios::sync_with_stdio(false);

    memset(path, -1, sizeof path);

    cin >> n;

    for(int i(1); i <= n; ++i)
    	cin >> a[i];

    cin >> m;

    for(int i(1); i <= m; ++i)
    	cin >> b[i];

    for(int i(1); i <= n; ++i)
    	for(int j(1), mx(0), tmp(-1); j <= m; ++j){
    		if(a[i] > b[j] && mx < dp[j])
    			mx = dp[j], tmp = j;

    		if(a[i] == b[j]){
    			dp[j] = mx+1, path[j] = tmp;

    			if(dp[j] > ans)
    				ans = dp[j], pos = j;
    		}
    	}

    cout << ans << endl;

    if(ans == 0)
        return 0;

    int cnt = 0;

    for(int j(pos); ~j; j = path[j])
    	ans1[++cnt] = b[j];

    for(int i(cnt); i > 0; --i)
    	cout << ans1[i] << ' ';

    return 0;
}
2025/7/21 17:03
加载中...