pat 1042. Shuffling Machine (20)

https://www.patest.cn/contests/pat-a-practise/1042

hash 一下顺序， 然后就是dp了。

#include <cstdio> #include <algorithm> using namespace std; #define rep(i,j,k) for(int i=j;i<=k;i++) #define inone(i) scanf("%d",&i) const int maxn = 1e4 + 10; int n, m, l, x, res, a[maxn], b[maxn], dp[maxn]; int main() { inone(n); rep(i, 1, n) a[i] = n + 1; inone(m); rep(i, 1, m) { inone(x); a[x] = i; } inone(l); rep (i, 1, l) inone(b[i]); rep(i, 1, l) rep(j, 0, i - 1) { if (a[b[i]] <= n && a[b[i]] >= a[b[j]]) dp[i] = max(dp[i], dp[j] + 1); } rep(i, 1, l) { if (a[b[i]] <= n) res = max(res, dp[i]); } printf("%d\n", res); return 0; }