2019 Multi

2019 Multi

暴力LIS

反着做比较好写，把解冻看成冻住，每次看冻住的位置是不是当前LIS中的位置，如果不是就直接删除，如果是，就暴力重新计算一次LIS

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define full(a, b) memset(a, b, sizeof a)
#define __fastIn ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
using namespace std;
using LL = long long;
inline int lowbit(int x){ return x & (-x); }
inline int read(){int ret = 0, w = 0; char ch = 0;while(!isdigit(ch)){w |= ch == '-', ch = getchar();}while(isdigit(ch)){ret = (ret << 3) + (ret << 1) + (ch ^ 48);ch = getchar();}return w ? -ret : ret;
}
template <typename A>
inline A __lcm(A a, A b){ return a / __gcd(a, b) * b; }
template <typename A, typename B, typename C>
inline A fpow(A x, B p, C lyd){A ans = 1;for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;return ans;
}
const int N = 50005;
int _, n, a[N], fr[N], dp[N], f[N], lis, ans[N];
bool vis[N], pos[N];void calc(){full(f, INF), full(dp, 0), lis = 0;for(int i = 1; i <= n; i ++){if(!vis[i]) continue;int p = (int)(lower_bound(f + 1, f + n + 1, a[i]) - f);if(f[p] == INF){f[p] = a[i], dp[i] = p;lis = max(lis, p);}else{f[p] = a[i], dp[i] = p;}}full(pos, false);int len = lis;for(int i = n; i >= 1; i --){if(!vis[i]) continue;if(!lis) break;if(dp[i] == len){pos[i] = true, len --;}}
}int main(){for(_ = read(); _; _ --){n = read();for(int i = 1; i <= n; i ++) a[i] = read();for(int i = 1; i <= n; i ++) fr[i] = read();full(vis, true), full(ans, 0);calc();for(int i = n; i >= 1; i --){ans[i] = lis;vis[fr[i]] = false;if(pos[fr[i]]) calc();}for(int i = 1; i <= n; i ++)printf("%d%c", ans[i], " n"[i == n]);}return 0;
}

转载于:.html