如何做网站同步,wordpress 做 cms,wordpress提示更新英文吧,悬赏做海报的网站一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
582B - Once Again... 二、解题报告
1、思路分析
考虑朴素做法对T *n的数组求LIS
但是T * n可达1e9
思考一下#xff0c;最优解无非就是几个循环节拼接#xff0c;我们最差情况下对sqrt(T)个a[]求LIS即…一、题目
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()
