LIS+找规律，CF 582B - Once Again...

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

582B - Once Again...

---

二、解题报告

1、思路分析

考虑朴素做法对T *n的数组求LIS

但是T * n可达1e9

思考一下，最优解无非就是几个循环节拼接，我们最差情况下对sqrt(T)个a[]求LIS即可

事实上，我们最多对n个a求LIS就能得到正确解

当然，即使对sqrt(T)个a求LIS也不会超时

2、复杂度

时间复杂度： O()空间复杂度：

3、代码详解

 ​

import sys
from bisect import bisect_left
from bisect import bisect_rightinput = lambda: sys.stdin.readline().strip()
MII = lambda: map(int, input().split())
LMI = lambda: list(map(int, input().split()))
P = 998244353def solve():n, T = MII()a = LMI()res = 0lis = []delta = 0for _ in range(n):delta = len(lis)for x in a:idx = bisect_right(lis, x)if idx < len(lis):lis[idx] = xelse:lis.append(x)delta = len(lis) - deltaT -= 1if not T:breakprint(len(lis) + delta * T)if __name__ == "__main__":solve()