読者です 読者をやめる 読者になる 読者になる

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();
    }
}