對局匹配 線性DP-分塊

題目鏈接

對局匹配

思路

? 當\(num = 0\)時， 答案為不重復的數字數量之和。

? 當\(num > 0\)時， 我們以模數不同將該序列劃分成不同的塊，即構造\(x + tk, (t = 0, 1, 2, \dots), x \in [0, k)\)， 以\(x\)來劃分不同的塊，這樣不同的塊一定能夠保證他們之間不會差\(k\), 因為相差等于\(k\)一定同余， 所以我們只考慮組內相差等于\(k\)， 這時就可以當成線性\(dp\)來做了, 對于組內我們用下列式子：

? 復雜度\(O(n)\)

Code

#include <bits/stdc++.h>

using i64 = long long;

const int N = 1e5 + 10;

int n, k;

int a[N], count[N], dp[N], val[N];

int main() {
	std::cin >> n >> k;

	for (int i = 1; i <= n; i ++) std::cin >> a[i], count[a[i]] ++;

	int ans = 0;

	if (!k) {
		for (int i = 1; i <= 1e5; i ++) {
			ans += (count[i] >= 1);
		}
	} else {
		for (int i = 0; i < k; i ++) {
			memset(dp, 0, sizeof dp);
			int cnt = 1;

			for (int j = i; j <= 1e5; j += k) {
				val[++ cnt] = count[j];
			}

			for (int j = 2; j <= cnt; j ++) {
				dp[j] = std::max(dp[j - 1], dp[j - 2] + val[j]);
			}

			ans += dp[cnt];
		}

	}

	std::cout << ans;
}