题解：AT_abc403_d [ABC403D] Forbidden Difference

· · 题解

大概题意：

将一个整数序列删除至对于每个数都没有比它大 D 和比它小 D 的数，求最少删除次数。

正式开始：

阅读完题我们可以发现：对于每个数，决定它是否被删除取决于比它大 D 和小 D 的数的个数，我们可能会想到一个贪心：对于每个数，删除与它相同的数或者与它大或小 D 的数中个数更少的那一个，但是我们难以保证这样是对的，但是这个方法给了我们一个灵感：既然贪心不行，那 dp 呢？

对于一个数又要考虑比它大 D 又要考虑比它小 D 的数是很难受的，但是我们可以只考虑比它小的，每个都只考虑比它小 D 的数，那也不会出错。我们设 dp[i][0] 是对于第 i 个数，删除比它小 D 的最少删除次数，dp[i][1] 是对于第 i 个数，删除它自己的最少删除次数。我们可以拿一个数组 v[1000005] 存储每个值在序列里出现的次数，为了优化，我们可以用 mx 来记录序列里最大的数，mn 记录最小的数，先预处理 mn\sim mn+D-1，再从 mn+D 开始 dp，答案就是 \sum_{i=mx-D+1}^{mx}\min(dp[i][0],dp[i][1])。

dp 转移方程也可以列出来了：

dp[i][0]=\min(dp[i-d][0]+v[i-d],dp[i-d][1])\\ dp[i][1]=\min(dp[i-d][0]+v[i],dp[i-d][1]+v[i])

但是对于这道题有很坑的点：D=0，对于这种情况，我们可以发现：让在序列里出现过的每个值都只剩下一个数，所以答案加上出现过的每个值出现的次数减一就可以了。

最后要注意统计答案时要注意 mx-D+1<0 的情况防止越界，贴出代码：

//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 1000005
#define M 1000000007
using namespace std;
inline ll read()
{
    ll x = 0, f = 1;
    char ch = gr();
    while (ch < '0' || ch > '9') ch == '-' ? f = -1, ch = gr() : ch = gr();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = gr();
    return x * f;
}
inline void write(ll x, bool k)
{
    static int sta[39], top = 0;
    if (x < 0) pr('-'), x = -x;
    do sta[++top] = x % 10, x /= 10;
    while (x);
    while (top) pr(sta[top--] + 48);
    k ? pr(32) : pr(10);
}
ll a[N], v[N];
ll dp[N][2];//删前，删自
int main()
{
    ll n = read(), d = read(), mx = 0, mn = M;
    ll ans = 0;
    for (rnt i = 1; i <= n; i++) a[i] = read(), v[a[i]]++, mx = max(mx, a[i]), mn = min(mn, a[i]);
    if (!d)
    {
        for (rnt i = mn; i <= mx; i++) ans += v[i] ? v[i] - 1 : 0;
        write(ans, 0);
    }
    else
    {
        for (rnt i = mn; i < mn + d; i++)
            dp[i][1] = v[i];
        for (rnt i = mn + d; i <= mx; i++)
        {
            dp[i][0] = min(dp[i - d][0] + v[i - d], dp[i - d][1]);
            dp[i][1] = min(dp[i - d][0] + v[i], dp[i - d][1] + v[i]);
        }
        for (rnt i = mx; i >= max(0ll, mx - d + 1); i--)//这里要判断，防止越界
            ans += min(dp[i][0], dp[i][1]);
        write(ans, 0);
    }
    return 0;
}

感谢您的观看！