UVA 1471 Defense Lines 防线（LIS变形）

给一个长度为n的序列，要求删除一个连续子序列，使剩下的序列有一个长度最大的连续递增子序列。

最简单的想法是枚举起点j和终点i，然后数一数，分别向前或向后能延伸的最长长度，记为g(i)和f(i)。可以先预处理出每一个点能往前和往后延伸的长度(g(i)和f(i))。然后枚举终点i，快速找一个g(j)最大的起点。如果有两个候选的起点，一个j，一个j‘，A[j']<=A[j]且g[j']>g[j]，那么j一定可以排除，g(j')更大，而且更容易拼接。

固定i的情况下，所有有价值的(A[j],g(j))按照A[j]排序（A[j]相同的值保留g(j)大的那个），将会形成一个有序表，根据之前的结论g(j)是递增的，有序，那么二分查找就派上用处了。

然后再考虑，变动i对之前的有序表的影响，i增加，把之前的A[i],g(i)加入到有序表中，如果满足A[i']比它A[i]小且g(i')最大的二元组，即它前面的一个元素，满足g(i')>=g(i)，那么这个元素不该保留。否则应该加入这个二元组，加入这个二元组之后，为了保持有序表的性质，还要往后检查删除一些g(i*)小的元素。

终于想得比较透彻了，实现方式是set，用pair来保证二元组，pair比较的时候是先比较第一维，相等时才比较第二维。至于第二种实现，用数组保存g(j)对应最小的A[j]值，复习LIS时再补上吧~

#include<bits/stdc++.h>

#define MP make_pair

#define se second

#define fi first

using namespace std;

const int maxn = 2e5+;

typedef pair<int,int> pii;

int A[maxn];

int g[maxn];//<-

int f[maxn];//->

//set<pii> s;

map<int,int> s;

int main()

{

    int T; scanf("%d",&T);

    while(T--){

        int n; scanf("%d",&n);

        for(int i = ; i < n; i++) scanf("%d",A+i);

        if(n == ) { printf("1\n"); continue; }

        g[] = ;

        for(int i = ; i < n; i++) {

            if(A[i]>A[i-]) g[i] = g[i-]+;

            else g[i] = ;

        }

        f[n-] = ;

        for(int i = n-; i >= ; i--) {

            if(A[i]<A[i+]) f[i] = f[i+]+;

            else f[i] = ;

        }

        s.clear(); s.insert(MP(A[],g[]));

        int ans = ;

        for(int i = ; i < n; i++){

            //pii cur(A[i],g[i]);

            map<int,int>::iterator it = s.lower_bound(A[i]);

            bool keep = true;

            if(it!=s.begin()){

                it--;

                ans = max(ans,it->se+f[i]);

                keep = it->se < g[i];

            }

            if(keep){

                //s.erase(cur);

                it = s.insert({A[i],g[i]}).fi;

                it++;

                while(it != s.end() && it->se <= g[i] ) s.erase(it++);

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

set_插入前要erase，因为set里的元素是不支持修改的，insert的返回值是itertor,bool

#include<bits/stdc++.h>

#define MP make_pair

#define se second

#define fi first

using namespace std;

const int maxn = 2e5+;

typedef pair<int,int> pii;

int A[maxn];

int g[maxn];//<-

int f[maxn];//->

set<pii> s;

int main()

{

    int T; scanf("%d",&T);

    while(T--){

        int n; scanf("%d",&n);

        for(int i = ; i < n; i++) scanf("%d",A+i);

        if(n == ) { printf("1\n"); continue; }

        g[] = ;

        for(int i = ; i < n; i++) {

            if(A[i]>A[i-]) g[i] = g[i-]+;

            else g[i] = ;

        }

        f[n-] = ;

        for(int i = n-; i >= ; i--) {

            if(A[i]<A[i+]) f[i] = f[i+]+;

            else f[i] = ;

        }

        s.clear(); s.insert(MP(A[],g[]));

        int ans = ;

        for(int i = ; i < n; i++){

            pii cur(A[i],g[i]);

            set<pii>::iterator it = s.lower_bound(cur);

            bool keep = true;

            if(it!=s.begin()){

                it--;

                ans = max(ans,it->se+f[i]);

                keep = it->se < cur.se;

            }

            if(keep){

                s.erase(cur);

                it = s.insert(cur).fi;

                it++;

                while(it != s.end() && it->se <= cur.se ) s.erase(it++);

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

类似LIS的写法，非常简洁的感觉

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5+;

int f[maxn],g[maxn];//前，后

int a[maxn];

int v[maxn];

const int INF = 0x3f3f3f3f;

int main()

{

    int Z; cin>>Z;

    while(Z--){

        int n; scanf("%d",&n);

        for(int i = ; i < n; i++) scanf("%d",a+i);

        f[] = ;

        for(int i = ; i < n; i++)

            f[i] =  + (a[i] > a[i-] ? f[i-] : );

        g[n-] = ;

        for(int i = n-; i--; )

            g[i] =  + (a[i] < a[i+] ? g[i+] : );

        int ans = ;

        for(int i = ; i < n; i++){

            v[+i] = INF;

            int k = lower_bound(v+,v++i,a[i])-v-;

            ans = max(ans,k+g[i]);

            v[f[i]] = min(v[f[i]],a[i]);

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

UVA 1471 Defense Lines 防线（LIS变形）

最新文章

热门文章

巴特西

UVA 1471 Defense Lines 防线 （LIS变形）

最新文章

热门文章

UVA 1471 Defense Lines 防线（LIS变形）