#include using namespace std;

const int N = 1e6 + 10; int cnt[N];

int main() { int n, m, ans = 0; cin >> n >> m; for (int i = 1; i <= n; i++) { int x; cin >> x; cnt[x]++; } if (m == 0) { for (int i = 0; i <= 1e6; i++) { if (cnt[i] >= 1) ans += cnt[i] - 1; } cout << ans << endl; return 0; } /* dp[i][0/1] 第i个拿/不拿时，最少删多少个 拿第i个：dp[i][0] = dp[i-1][1] 不拿第i个: dp[i][1] = (dp[i-1][0] or dp[i-1][1]) + 第i个的数量 / for (int i = 0; i < m; i++) { //枚举第一个数字是什么 //那么之后的数字都是 i + jm的形式 int dp1 = 0, dp2 = 0; // 这里原来的dp3可能是笔误，根据状态转移，只需要两个变量 for (int j = 0; ; j++) { // 循环条件改为无限循环，内部判断是否越界 int num = i + j * m; if (num > 1e6) break; // 超过范围就退出 int temp = dp1; // 保存dp1原来的值 dp1 = min(dp2, dp1) + cnt[num]; // 不拿当前数，转移 dp2 = temp; // 拿当前数，转移 } ans += min(dp1, dp2); // 取两种状态的最小值 } cout << ans; return 0; } #include using namespace std;

const int N = 1e6 + 10; int cnt[N];

int main() { int n, m, ans = 0; cin >> n >> m; for (int i = 1; i <= n; i++) { int x; cin >> x; cnt[x]++; } if (m == 0) { for (int i = 0; i <= 1e6; i++) { if (cnt[i] >= 1) ans += cnt[i] - 1; } cout << ans << endl; return 0; } /* dp[i][0/1] 第i个拿/不拿时，最少删多少个 拿第i个：dp[i][0] = dp[i-1][1] 不拿第i个: dp[i][1] = (dp[i-1][0] or dp[i-1][1]) + 第i个的数量 / for (int i = 0; i < m; i++) { //枚举第一个数字是什么 //那么之后的数字都是 i + jm的形式 int dp1 = 0, dp2 = 0; // 这里原来的dp3可能是笔误，根据状态转移，只需要两个变量 for (int j = 0; ; j++) { // 循环条件改为无限循环，内部判断是否越界 int num = i + j * m; if (num > 1e6) break; // 超过范围就退出 int temp = dp1; // 保存dp1原来的值 dp1 = min(dp2, dp1) + cnt[num]; // 不拿当前数，转移 dp2 = temp; // 拿当前数，转移 } ans += min(dp1, dp2); // 取两种状态的最小值 } cout << ans; return 0; } #include using namespace std;

const int N = 1e6 + 10; int cnt[N];

int main() { int n, m, ans = 0; cin >> n >> m; for (int i = 1; i <= n; i++) { int x; cin >> x; cnt[x]++; } if (m == 0) { for (int i = 0; i <= 1e6; i++) { if (cnt[i] >= 1) ans += cnt[i] - 1; } cout << ans << endl; return 0; } /* dp[i][0/1] 第i个拿/不拿时，最少删多少个 拿第i个：dp[i][0] = dp[i-1][1] 不拿第i个: dp[i][1] = (dp[i-1][0] or dp[i-1][1]) + 第i个的数量 / for (int i = 0; i < m; i++) { //枚举第一个数字是什么 //那么之后的数字都是 i + jm的形式 int dp1 = 0, dp2 = 0; // 这里原来的dp3可能是笔误，根据状态转移，只需要两个变量 for (int j = 0; ; j++) { // 循环条件改为无限循环，内部判断是否越界 int num = i + j * m; if (num > 1e6) break; // 超过范围就退出 int temp = dp1; // 保存dp1原来的值 dp1 = min(dp2, dp1) + cnt[num]; // 不拿当前数，转移 dp2 = temp; // 拿当前数，转移 } ans += min(dp1, dp2); // 取两种状态的最小值 } cout << ans; return 0; }

思路：

• 首先这题如果要删除数字 $x$ ，一定是把所有的数字 $x$ 都删掉。
• 对于数字 $x$（ $x < d$ ），会对答案造成影响的其实是数列 $x, x + d, x + 2 * d \dots$，并且删除其中一些数字后，剩下的数字不能相邻。
• 所以问题就转化为：确定 $x$ 后，需要从数列中删除尽可能少的数字，使删除后不存在相邻的数。
• 这个问题可以用 $dp$ 解决。
  $dp[i][0/1]$ 表示考虑前 $i$ 个数，第 $i$ 个数是删 / 不删，最少需要操作几次。
  $dp[i][0] \leftarrow dp[i - 1][1]$，第 $i$ 个不删，则第 $i - 1$ 个一定得删。
  $ dp[i][1] \leftarrow \min(dp[i - 1][0], dp[i - 1][1]) + cnt $，第 $i$ 个删，那么第 $i - 1$ 个删不删都行，$cnt$ 是第 $i$ 个数字的个数。

做法：

• 特殊处理 $d = 0$ 的情况，此时每种数字只能删得只剩一个。
• 先存每个数字总共出现的次数，再枚举第一个数字 $x$，开始 $dp$。
• 因为 $dp[i][0/1]$ 只和 $dp[i - 1][0/1]$ 有关，所以直接用变量存 $dp$ 值，不开数组。

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int cnt[N];

int main() {
    int n, m, ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    if (m == 0) {
        for (int i = 0; i <= 1e6; i++) {
            if (cnt[i] >= 1) ans += cnt[i] - 1;
        }
        cout << ans << endl;
        return 0;
    }
    /*
        dp[i][0/1] 第i个拿/不拿时，最少删多少个
        拿第i个：dp[i][0] = dp[i-1][1]
        不拿第i个: dp[i][1] = (dp[i-1][0] or dp[i-1][1])  + 第i个的数量
    */
    for (int i = 0; i < m; i++) { //枚举第一个数字是什么
        //那么之后的数字都是 i + j*m的形式
        int dp1 = 0, dp2 = 0; // 这里原来的dp3可能是笔误，根据状态转移，只需要两个变量
        for (int j = 0; ; j++) { // 循环条件改为无限循环，内部判断是否越界
            int num = i + j * m;
            if (num > 1e6) break; // 超过范围就退出
            int temp = dp1; // 保存dp1原来的值
            dp1 = min(dp2, dp1) + cnt[num]; // 不拿当前数，转移
            dp2 = temp; // 拿当前数，转移
        }
        ans += min(dp1, dp2); // 取两种状态的最小值
    }
    cout << ans;
    return 0;
}