ブルーブリッジカップ2017国試合B組C/C+【対局マッチング】

a[i]とa[i]+kがすべての要素の間でkの差が同時に現れない要素は同時に現れないという制約条件をできるだけ取りましょう.
取れる最大の数の和を求めてみましょう
分析:dpの考え方、これは木の形のdpと少し似ています0~kを列挙してそれから各この要素の上で反復してkをプラスして各要素は2つの状態を保存して繰返しを考慮してみてください
可能な限り多くの数を選択するだけです.つまり、この要素がこのような大きな要素をすべて選択できる場合、つまり、これらの要素の数を事前に統計して、実行可能なデータを計算するときに直接使用します.
この要素を取ると彼はdp[i][1]=dp[i-k][0]+numberに等しい.i
この要素を取らなければ、彼はdp[i][0]=max(dp[i-k][0],dp[i-k][1])の2つの選択が最大に移行することになる.
それぞれの記録を取るか取らないかで情報を蓄積することができます

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;


public class Main {
	static Scanner sc = new Scanner(new BufferedInputStream(System.in));
	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	static int a[] = new int[100010];
	static int dp[][] = new int[100010][2];

	public static void main(String[] args) {
		int n, k;
		n = sc.nextInt();
		k = sc.nextInt();
		int ma = -1;
		for (int i = 1; i <= n; i++) {
			int t = sc.nextInt();
			a[t]++;
			ma = Math.max(ma, t);
		}

		int sum = 0;
		if (k == 0) {
			for (int i = 0; i <= ma; i++)
				if (a[i] != 0)
					sum++;
		} else {
			for (int i = 0; i < k; i++) {
				for (int j = i; j <= ma; j += k) {
					if (j < k) {
						dp[j][0] = 0;
						dp[j][1] = a[i];
					} else {
						dp[j][0] = Math.max(dp[j - k][0], dp[j - k][1]);
						dp[j][1] = dp[j - k][0] + a[j];
						if (j + k > ma)
							sum += Math.max(dp[j][0], dp[j][1]);
					}
				}
			}
		}
		out.println(sum);
		out.flush();
	}
}