CodeForces - 583D Once Again... LIS 循环

题意：给你n个数（n<=100,a_i<=300) 一个T，求n重复T次的最长非递减子序列。

题解：我直接考虑4 3 2 1 的例子，当其重复4次时会出现1 2 3 4 的子序列，此时再怎么重复，这也是最长的递增序列，无非是多出（T-n)个1.

　　所以直接不完全（不会证明地）归纳处一个答案：ans=T>n?（T-n)*M+lis(a,n*n):lis(a,n*T) .M是n个数中重复次数最多的数，lis函数输出a数列的最长非递减子序列.（考虑如果重复最多的数并非最长子序列的起始数的情况：比如1244，观察最后四个循环1244124412441244，lis不再是1244，而会自动变成44444444，所以大概是不用考虑的，反正是猜想，交一发试试呗）

坑：第一次没考虑序列重复的情况（看到a_i<=300还以为是桶排）；

然后ans的公式手抽写错了写成（T-1）；

最后发现

c++17.0会wa2

clang 17 dignosed 会报list的错改好后MLE 1

c++14.0缺AC了 OTZ

ac：

#define  _CRT_SECURE_NO_WARNINGS

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<string>

#include<vector>

#include<string.h>

using namespace std;

typedef long long ll;

const int maxn =  + ;

int lis[maxn*maxn], a[maxn*maxn];

int c[], M;

int list(int arr[], int n)

{

    int i, j, max;

    max = ;

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

        lis[i] = ;

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

    {

        for (j = ; j<i; j++)

        {

            if (arr[i] >= arr[j] && lis[i]<lis[j] + )

                lis[i] = lis[j] + ;

        }

    }

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

        if (max < lis[i])

            max = lis[i];

    return max;

}

int main() {

    int n, t; int M;

    cin >> n >> t;

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

        cin >> a[i], c[a[i]]++, M = max(M, c[a[i]]);

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

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

            a[i*n + j] = a[j];

        }

    }

    if (t > n)cout << (t - n)*M + list(a, n*n) << endl;

    else {

        cout << list(a, n*t) << endl;

        //for (int i = 1; i <= t*n; i++)cout << a[i];

    }

    cin >> n;

}

巴特西

CodeForces - 583D Once Again... LIS 循环

最新文章

热门文章