You are given an array of positive integers a1, a2, ..., an × T of length n × T. We know that for any i > n it is true that ai = ai - n. Find the length of the longest non-decreasing sequence of the given array.
The first line contains two space-separated integers: n, T (1 ≤ n ≤ 100, 1 ≤ T ≤ 107). The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 300).
Print a single number — the length of a sought sequence.
4 3 3 1 4 2
5
The array given in the sample looks like that: 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4, 2. The elements in bold form the largest non-decreasing subsequence.
题目大意：给出一个长度为n的序列a，求由T个序列a连接起来形成的新序列的最长不降子序列。
易知求出的序列的形态一定是前后若干个元素加上中间若干个相同的元素。因为每个循环节中至少要取一个元素（取一定比不取优），所以可以分别正着和倒着DP长度为n*n的序列，然后再枚举求解。
代码在此。
评论 (0)
