對局匹配 線性DP-分塊
題目鏈接
思路
? 當\(num = 0\)時, 答案為不重復的數字數量之和。
? 當\(num > 0\)時, 我們以模數不同將該序列劃分成不同的塊,即構造\(x + tk, (t = 0, 1, 2, \dots), x \in [0, k)\), 以\(x\)來劃分不同的塊,這樣不同的塊一定能夠保證他們之間不會差\(k\), 因為相差等于\(k\)一定同余, 所以我們只考慮組內相差等于\(k\), 這時就可以當成線性\(dp\)來做了, 對于組內我們用下列式子:
\[dp[j] = std::max(dp[j - 1], dp[j - 2] + count[j])
\]
? 復雜度\(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;
}
浙公網安備 33010602011771號