Codeforces #323 D. Once Again... (LIS)

タイトル:
T<=107サイクルのN<=100のシーケンスを与えて、このシーケンスのLISを求めます
分析:
シーケンスa 1,𔁛anTには最大n個の異なる元素があり、そのいずれかの減少しないサブシーケンスには最大n −𔁛1個の上昇元素対がある.これにより、前nサイクル(a 1,̵...,̵an2)、後nサイクル(anT̵−̵n̵+̵1,̵...,̵anT)のLISを先に前処理することができる.f[i]:=a[i]で終わる前n周期のLISの最大長g[i]:=a[i]で始まる後n周期のLISの最大長ans=max{f[i]+(T−2 n)count(ai)+max{g[j],aj>=ai∩j∈[nT−n+1,nT]},i∈[1,n 2]}ps:count(ai)=cnt of ai in a 1,...,anはどのようにこれを求めて、まあ、この1つのとても明らかなsetは貪欲で辛くて、sortは条件を満たすg[j]の最大値を維持して、それから絶えずansを更新します
コード:

//
// Created by TaoSama on 2015-10-04
// Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, T, a[N], f[N], g[N], h[N], cnt[305];
//f: end i g: start i

int r[N];
bool cmp(int x, int y) {
    return a[x] > a[y];
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(scanf("%d%d", &n, &T) == 2) {
        memset(cnt, 0, sizeof cnt);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
            ++cnt[a[i]];
        }
        int t = min(T, n << 1);
        for(int i = 1; i < t; ++i)
            for(int j = 1; j <= n; ++j)
                a[j + i * n] = a[j];

        int ans = 0;
        if(T <= n << 1) {
            memset(h, 0x3f, sizeof h);
            for(int i = 1; i <= n * t; ++i) {
                int k = upper_bound(h + 1, h + n * t + 1, a[i]) - h;
                ans = max(ans, k);
                h[k] = a[i];
            }
        } else {
            memset(h, 0x3f, sizeof h);
            for(int i = 1; i <= n * n; ++i) {
                int k = upper_bound(h + 1, h + n * n + 1, a[i]) - h;
                f[i] = k;
                h[k] = a[i];
            }

            memset(h, 0x3f, sizeof h);
            for(int i = n * n; i; --i) {
                int k = upper_bound(h + 1, h + n * n + 1, -a[i]) - h;
                g[i] = k;
                h[k] = -a[i];
            }

            for(int i = 1; i <= n * n; ++i) r[i] = i;
            sort(r + 1, r + n * n + 1, cmp);
            set<int> s;
            for(int i = 1, j = 1; i <= n * n; ++i) {
                int x = r[i];
                while(j <= n * n && a[r[j]] >= a[r[i]]) s.insert(g[r[j++]]);
                int tmp = f[x] + (T - 2 * n) * cnt[a[x]] + (*s.rbegin());
                ans = max(ans, tmp);
            }
        }
        printf("%d
", ans);
    }
    return 0;
}

UPD:実は暴力n段は、最も多くの挿入中間もacできるが、正確性はそれほど明らかではない.

//
// Created by TaoSama on 2015-10-04
// Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, T, a[N], g[N];
int cnt[305];

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(scanf("%d%d", &n, &T) == 2) {
        memset(cnt, 0, sizeof cnt);
        int maxv = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
            maxv = max(maxv, ++cnt[a[i]]);
        }
        int t = min(T, n);
        for(int i = 1; i < t; ++i)
            for(int j = 1; j <= n; ++j)
                a[j + i * n] = a[j];

        memset(g, 0x3f, sizeof g);
        int ans = 0;
        for(int i = 1; i <= n * t; ++i) {
            int k = upper_bound(g + 1, g + n * t + 1, a[i]) - g;
            ans = max(ans, k);
            g[k] = a[i];
        }

        ans += maxv * (T - t);
        printf("%d
", ans);
    }
    return 0;
}