湘潭邀请赛 2018 I Longest Increasing Subsequence

题意：

　　给出一个长度为n的序列，序列中包含0。定义f(i)为把所有0变成i之后的Lis长度，求)。

题解：

　　设不考虑0的Lis长度为L，那么对于每个f(i)，值为L或L+1。

　　预处理f[j]，g[j]代表在第j个数结束和从第j个数开始的Lis长度。

　　对于（1~n）的每个j，找到一个最大的a[k]（k>j且a[k]>a[j]），使得g[j]+f[k] = L且j和k之间存在0。那么(a[j]，a[k])区间内的数的f()值即为L+1。

　　从后面往前扫，对于当前点j，vis[L-a[j]]即为最大的a[k]。每到一个0就更新上一个0到这个0的vis信息，保证了j和k之间一定存在着0。若vis[L-a[j]]>a[j]，则用差分的形式对（a[j]，vis[L-a[j]]）区间进行+1。

最后维护下前缀和判断f()的值。还有两种是0 2 和 2 0 这种前缀0和后缀0的情况要特判一下。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
int n, pos;
int L;
int a[N];
int f[N], g[N], vis[N];
ll sum[N];
ll ans, cnt;
int main() {
    while(~scanf("%d", &n)) {
        L = 0;
        ans = cnt = 0;
        for(int i = 1; i <= n; i++) vis[i] = inf;
        for(int i = 1; i <= n; i++) sum[i] = 0;
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]), cnt+=a[i];
        if(!cnt) {
            printf("%lld
", 1ll*n*(n+1)/2);
            continue;
        }
        for(int i = 1; i <= n; i++) {
            if(!a[i]) continue;
            int p = lower_bound(vis+1, vis+n+1, a[i])-vis;
            L  = max(L, p);
            vis[p] = a[i];
            f[i] = p;
        }
        for(int i = 1; i <= n; i++) vis[i] = inf;
        for(int i = n; i >= 1; i--) {
            if(!a[i]) continue;
            int p = lower_bound(vis+1, vis+n+1, -a[i])-vis;
            vis[p] = -a[i]; 
            g[i] = p;
        }
        for(int i = 1; i <= n; i++) vis[i] = 0;
        pos = n+1;
        for(int i = n; i >= 1; i--) {
            if(a[i]&&pos!=n+1) {
                if(f[i]==L) sum[a[i]+1]++; 
                else if(vis[L-f[i]]>a[i]+1) sum[a[i]+1]++, sum[vis[L-f[i]]]--; 
            } 
            else if(!a[i]) {
                for(int j = pos-1; j > i; j--) vis[g[j]] = max(vis[g[j]], a[j]);
                pos = i;
            }
        }
        int pos = 0;
        for(int i = 1; i <= n; i++) {
            if(pos&&a[i]&&g[i]==L) sum[1]++, sum[a[i]]--;
            if(!a[i]) pos++; 
        }
        for(int i = 2; i <= n; i++) sum[i] += sum[i-1];
        for(int i = 1; i <= n; i++) {
            if(sum[i]) ans += 1ll*i*(L+1);
            else ans += 1ll*i*L;
        }
        printf("%lld
", ans);
    }
}

View Code

湘潭邀请赛 2018 I Longest Increasing Subsequence

相关推荐