湘潭邀请赛 2018 I Longest Increasing Subsequence

题意：

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

题解：

　　设不考虑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+;

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 = ;

        ans = cnt = ;

        for(int i = ; i <= n; i++) vis[i] = inf;

        for(int i = ; i <= n; i++) sum[i] = ;

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

        if(!cnt) {

            printf("%lld\n", 1ll*n*(n+)/);

            continue;

        }

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

            if(!a[i]) continue;

            int p = lower_bound(vis+, vis+n+, a[i])-vis;

            L  = max(L, p);

            vis[p] = a[i];

            f[i] = p;

        }

        for(int i = ; i <= n; i++) vis[i] = inf;

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

            if(!a[i]) continue;

            int p = lower_bound(vis+, vis+n+, -a[i])-vis;

            vis[p] = -a[i];

            g[i] = p;

        }

        for(int i = ; i <= n; i++) vis[i] = ;

        pos = n+;

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

            if(a[i]&&pos!=n+) {

                if(f[i]==L) sum[a[i]+]++;

                else if(vis[L-f[i]]>a[i]+) sum[a[i]+]++, sum[vis[L-f[i]]]--;

            }

            else if(!a[i]) {

                for(int j = pos-; j > i; j--) vis[g[j]] = max(vis[g[j]], a[j]);

                pos = i;

            }

        }

        int pos = ;

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

            if(pos&&a[i]&&g[i]==L) sum[]++, sum[a[i]]--;

            if(!a[i]) pos++;

        }

        for(int i = ; i <= n; i++) sum[i] += sum[i-];

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

            if(sum[i]) ans += 1ll*i*(L+);

            else ans += 1ll*i*L;

        }

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

    }

}

巴特西

湘潭邀请赛 2018 I Longest Increasing Subsequence

最新文章

热门文章