Codeforces Round #323 Div2 D: Once Again...
解法
増加列に含まれる値の種類は多くてN種類なので、T>Nならば、最も多い種類の点の数を (T-N) 回足せば良い。
コード
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Scanner; import java.util.TreeSet; public class Main { public void solve() { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int T = scanner.nextInt(); int[] data = new int[N]; for (int i = 0; i < N; i++) { data[i] = scanner.nextInt(); } scanner.close(); // なんとなく座標圧縮 { TreeSet<Integer> set = new TreeSet<>(); for (int d : data) { set.add(d); } ArrayList<Integer> list = new ArrayList<>(set); for (int i = 0; i < N; i++) { data[i] = Collections.binarySearch(list, data[i]); } } int[] dp = new int[N]; int ans = 0; for (int i = 0; i < Math.min(T, N); i++) { // i配列目のdata[j]で終わるときのLISを求める for (int j = 0; j < N; j++) { for (int k = data[j]; k >= 0; k--) { dp[data[j]] = Math.max(dp[data[j]], dp[k] + 1); } ans = Math.max(ans, dp[data[j]]); } } int[] cnt = new int[N]; for (int d : data) cnt[d]++; Arrays.sort(cnt); ans += cnt[N - 1] * Math.max(0, T - N); System.out.println(ans); } public static void main(String[] args) { new Main().solve(); } }