icontofig | 发布于 2019-08-08 23:29:10 | 阅读量 275 | DP 回溯
发布于 2019-08-08 23:29:10 | DP 回溯

题目大意

给n个数,每个时刻就会有一个新的数可用,求每个时刻所有可用的数字按照序列位置组成的最长上升子序列长度。数据生成完全随机。

题解

由于数据完全随机生成,所以当所有数都可用的时候,LIS的期望长度是n1/2 。我们删掉一个数,这个数在LIS中的概率期望是1/n1/2

我们可以把原问题逆向来考虑,从一开始所有数可用,然后不断删除数字。

如果删除的数字在上一次的LIS中,则我们需要重新求一次LIS,否则就延续上一次的答案。

如果我们使用O(nlogn)方法的LIS,那么一组数据的总体时间复杂度就是O(n3/2logn)

这题因为手写二分写丑了没用lower_bound被卡T一次,然后因为行末空格被卡PE一次,AWSL。

代码


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 50005;
int T;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
int n;
int p[maxn],k[maxn],seq[maxn];
int ans[maxn],vis[maxn],ban[maxn],pre[maxn];
int len = 0;
int pos;
int work(){
    for(int i = 1;i <= len;++i)
        seq[i] = 0,vis[seq[i]] = 0;
    seq[0] = 0;
    len = 0;
    for(int i = 1;i <= n;++i){
        if(ban[i])
            continue;
        if(p[i]> seq[len]){
            len++;
            seq[len] = p[i];
            pre[p[i]] = seq[len-1];
        }
        else{
            int pos = lower_bound(seq+1,seq+len+1,p[i]) - seq;
            if(!pos)continue;
            seq[pos] = p[i];
            pre[p[i]] = seq[pos-1];
        }
    }
    int x = seq[len];
    while(x != 0){
        vis[x] = 1;
        x = pre[x];
    }
    return len;
}
int main(){
    T = get_num();
    while(T--){
        n = get_num();
        for(int i = 1;i <= len;++i)
            seq[i] = 0;
        for(int i = 1;i <= n;++i)
            p[i] = get_num();
        for(int i = 1;i <= n;++i){
            k[i] = get_num();
        }
        for(int i = 1;i <= n;++i){
            ans[i] = vis[i] = ban[i] = 0;
        }
        ans[n] = work();
        for(int i = n-1;i >= 1;--i){
            int t = k[i+1];
            ban[t] = 1;
            if(vis[p[t]])
                ans[i] = work();
            else ans[i] = ans[i+1];
        }
        printf("%d",ans[1]);
        for(int i = 2;i <= n;++i){
            printf(" %d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}

 


内容更新于: 2019-08-08 23:29:11
链接地址: http://blog.leanote.com/post/icontofig/99736dab265b

上一篇: Codeforces 1202B You Are Given a Decimal String... 最短路Floyd预处理

下一篇: CodeChef - ELHIDARR Find an element in hidden array 人机交互+二分

275 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航