题目描述

难度分:$1900$

输入$n(1 \leq n \leq 100)$、$t(1 \leq t \leq 10^7)$和长为$n$的数组$a(1 \leq a[i] \leq 300)$。

把$t$个一样的数组$a$拼接在一起，得到长为$t \times n$的数组$b$，满足$b[i]=b[i+n]$。

输出$b$的最长非降子序列（$LIS$）的长度。注意这里的$LIS$是非降的，允许元素相等。

输入样例

4 3
3 1 4 2

输出样例

5

算法

贪心+动态规划

看到这个题的$n$这么小就感觉不需要复制多少次，后面就只会选同一个数了。分为以下两种情况：

1. $T \leq n$，那直接构造出长度为$n \times t$的数组用二分优化的动态规划求$LIS$。
2. $T \gt n$，就只构造出长度为$n^2$的数组用二分优化的动态规划求$LIS$，剩下的$T-n$个副本都选众数出来即可。

下面解释一下为什么用$n$分类讨论，试想一下如果$n$个数组选出$n$个互不相同的数（假设数足够），后面$T-n$个副本就只会选同一个数了。而如果选出来的不是$n$个互不相同的数，那$LIS$的长度就会超过$n$，直接在$min(nT,n^2)$长度的数组上求就行，这个$LIS$中的数也一定覆盖住了原数组中所有的数值，因此后面$T-n$个副本也还是选同一个数值。

但是为什么最后选众数就可以，不需要考虑前$n$个副本的$LIS$以哪个数值结尾呢？因为这$n$个副本并不一定需要连续，最后$T-n$个副本不是非得选最大值。这样的话就可以选众数，如果这个众数不是最大值，就把选出来的数插在前$n$个副本$LIS$合适的位置上就可以了（相当于把$T-n$个副本插在了这$n$个副本之间）。

复杂度分析

时间复杂度

算法的瓶颈在于对长度为$min(nT,n^2)$的数组求$LIS$，经过了二分优化，时间复杂度为$O(min(nT,n^2)log_2min(nT,n^2))$。

空间复杂度

空间的瓶颈在于新数组所消耗的空间，其长度为$min(nT,n^2)$。因此，整个算法的额外空间复杂度为$O(min(nT,n^2))$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 110;
int T, n, a[N];

int lowerBound(vector<int>& nums, int left, int right, int target) {
    int index = right + 1;
    while(left <= right) {
        int mid = left + ((right - left) >> 1);
        if(nums[mid] > target) {
            index = mid;
            right = mid - 1;
        }else {
            left = mid + 1;
        }
    }
    return index;
}

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> ends(n, -1);
    ends[0] = nums[0];
    int size = 1, ans = 1;
    for(int i = 1; i < n; i++) {
        int index = lowerBound(ends, 0, size - 1, nums[i]);
        if(index == size) {
            size++;
        }
        ends[index] = nums[i];
        ans = max(ans, index + 1);
    }
    return ans;
}

int main() {
    scanf("%d%d", &n, &T);
    int cnt[301] = {0};
    int maxfreq = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        cnt[a[i]]++;
        maxfreq = max(maxfreq, cnt[a[i]]);
    }
    vector<int> nums;
    for(int j = 1; j <= min(n, T); j++) {
        for(int i = 1; i <= n; i++) {
            nums.push_back(a[i]);
        }
    }
    LL ans = lengthOfLIS(nums);
    if(T <= n) {
        printf("%lld\n", ans);
    }else {
        ans += 1LL*(T - n)*maxfreq;
        printf("%lld\n", ans);
    }
    return 0;
}