本文共 2394 字，大约阅读时间需要 7 分钟。
题意：给你一个n的排列，起初这些数都不能用， 然后还有一个数组 第 i 个数表示下标为 i 的数能够使用。
问每一个 i 对应的最长上升子序列。
题解：
可以通过倒推，从后往前考虑转化一下 ，然后就是删除一个数，两个数到n个数的最长上升子序列。
比赛的时候不会算复杂度算出来的是n^2log(n) ，完全不敢写，一直在想办法优化
赛后题解就是这个做法，但是题解说 因为数据随机，因此 LIS 的期望长度是 O( √ n)，
删除的 x 位于 LIS 中的概率是 √ 1 n，也就 是说期望删除 O( √ n) 个数才会修改 LIS，
那么 LIS 变化的次数不会很多。期望时间复杂度为 O(n √ n log n)。
LIS 的期望长度是 O( √ n)，有一个证明
（这个故事告诉我们敢写才能过，别想这么多，莽就是了）
这题就是纯暴力的样子了
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #define pi acos(-1.0)13 #define eps 1e-914 #define fi first15 #define se second16 #define rtl rt<<117 #define rtr rt<<1|118 #define bug printf("******\n")19 #define mem(a,b) memset(a,b,sizeof(a))20 #define name2str(x) #x21 #define fuck(x) cout<<#x" = "< < = b; i--)30 #define FRL(i,a,b) for(i = a; i < b; i++)+31 #define FRLL(i,a,b) for(i = a; i > b; i--)32 #define FIN freopen("data.txt","r",stdin)33 #define gcd(a,b) __gcd(a,b)34 #define lowbit(x) x&-x35 #define rep(i,a,b) for(int i=a;i =b;--i)37 using namespace std;38 typedef long long LL;39 typedef unsigned long long ULL;40 const int maxn = 100000 + 7;41 const int maxm = 8e6 + 10;42 const int mod = 1e9 + 7;43 const int INF = 0x3f3f3f3f;44 int T, n, a[maxn], b[maxn], vis[maxn], ans[maxn], len, dp[maxn], pre[maxn];45 void solve() {46 for ( int i = 0 ; i <= n ; i++ ) dp[i] = INF, pre[i] = 0, vis[i] = 0;47 dp[0] = 0;48 for ( int i = 1 ; i <= n ; i++ ) {49 if ( !a[i] ) continue;50 int pos = lower_bound ( dp + 1, dp + 1 + n, a[i] ) - dp;51 pre[a[i]] = dp[pos - 1];52 dp[pos] = a[i];53 }54 for ( int i = 1 ; i <= n ; i++ ) {55 if ( dp[i] != INF ) len = i;56 else break;57 }58 int x = dp[len];59 while ( x ) {60 vis[x] = 1;61 x = pre[x];62 }63 }64 int main() {65 sf ( T );66 while ( T-- ) {67 sf ( n );68 for ( int i = 1 ; i <= n ; i++ ) sf ( a[i] );69 for ( int i = 1 ; i <= n ; i++ ) sf ( b[i] );70 reverse ( b + 1, b + 1 + n );71 solve();72 ans[1] = len;73 for ( int i = 1 ; i < n ; i++ ) {74 if ( vis[a[b[i]]] ) {75 a[b[i]] = 0;76 solve();77 } else a[b[i]] = 0;78 ans[i + 1] = len;79 }80 reverse ( ans + 1, ans + 1 + n );81 for ( int i = 1 ; i <= n ; i++ ) printf ( "%d%c", ans[i], ( i == n ? '\n' : ' ' ) );82 }83 return 0;84 }
转载于:https://www.cnblogs.com/qldabiaoge/p/11317780.html
