1127.保安的苦恼

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define inf 0x3fffffff
using namespace std;

int f[101][101];
int w[101][101];
int t[101];
int n, m, r;

int dyna() {
    int i, j, k, tmp;

    sort(t + 1, t + n + 1);
    for (i = 1; i <= n; i++)
        for (j = i; j <= n; j++)
            for (k = i; t[j] - t[k] > r; k++)
                w[i][j] += t[j] - t[k] - r;

    for (i = 1; i <= n; i++)
        f[i][1] = w[1][i];
    for (j = 2; j <= m; j++) {
        for (i = j; i <= n; i++) {
            f[i][j] = inf;
            for (k = j - 1; k < i; k++) {
                tmp = f[k][j - 1] + w[k + 1][i];
                f[i][j] = min(f[i][j], tmp);
            }
        }
    }
    return f[n][m];
}

int main(int argc, char** argv) {
    int i;

    scanf("%d %d %d", &n, &m, &r);
    for (i = 1; i <= n; i++)
        scanf("%d", &t[i]);

    printf("%d\n", dyna());

    return 0;
}