NOIP2018普及组摆渡车题解

点击打开题目:

设计状态 : 设 f[i] 表示运完 i 之前的所有学生并且最后一辆车到的时间是 i 的答案.

$f_i = \min_{j \le i-m} \{f_j + \sum_{j < t_k \le i} i - t_k \}$

优化1:

$f_i = \min_{i - 2m < j \le i-m} \{f_j + \sum_{j < t_k \le i} i - t_k \}$

优化2:

if (i >= m && cnt[i - m] == cnt[i]) { f[i] = f[i - m]; continue; }

即可通过本题。
代码:

#include <bits/stdc++.h>
using namespace std;
const int T = 4000105;
int n, m, t, x, ans, cnt[T], sum[T], f[T];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        t = max(t, x);
        cnt[x] ++;
        sum[x] += x;
    }
    for (int i = 1; i < t + m; i++)
        cnt[i] += cnt[i - 1], sum[i] += sum[i - 1];
    for (int i = 0; i < t + m; i++)
    {
        if (i >= m && cnt[i - m] == cnt[i]) { f[i] = f[i - m]; continue; }
        f[i] = cnt[i] * i - sum[i];
        for (int j = max(i - 2 * m + 1, 0); j <= i - m; j++)
            f[i] = min(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]));
    }
    ans = 1e9;
    for (int i = t; i < t + m; i++)
        ans = min(ans, f[i]);
    printf("%d", ans);
    return 0;
}