Description

有n个人，要分成m个班，每个班至少1人。每班贡献为\((max-min)^2\)，求最小贡献值。
\(1<=N<=10000,1<=M<=1000，1<=Ai<=1000000\)

Solution

很容易想到\(DP\)。
由于我们要使贡献最小，所以我们不妨将它排序，然后每次取连续的一段，这样可以保证值最小。
这题由于要刚好分成\(m\)个班，所以我们必须要多设一维\(DP\)。
设\(f[i][j]\)表示到第\(i\)个人，往前分了\(j\)个班的最小贡献。
很容易得到转移方程：
\[f[i][j] = min(f[k][j - 1] + (a[i] - a[k + 1])^2)\]
时间为\(O(n^2m)\)，过不了，所以我们考虑优化。
斜率优化即可。
这题还可以用凸优化，但我不会。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 10010
#define M 1010
#define mem(x, a) memset(x, a, sizeof x)
#define fo(x, a, b) for (int x = a; x <= b; x++)
using namespace std;
int n, m, a[N], f[N][M], g[N], l = 1, len = 0;

inline int read()
{
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x;
}

int sqr(int x) {return x * x;}

int left(int x, int y, int k) {return f[x][k] - f[y][k] + sqr(a[x + 1]) - sqr(a[y + 1]);}

int right(int x, int y) {return 2ll * (a[x + 1] - a[y + 1]);}

int main()
{
    freopen("queue.in", "r", stdin);
    freopen("queue.out", "w", stdout);
    n = read(), m = read();
    fo(i, 1, n) a[i] = read();
    sort(a + 1, a + n + 1);
    mem(f, 10); 
    fo(i, 1, n) f[i][1] = sqr(a[i] - a[1]);
    fo(j, 2, m)
    {
        f[j][j] = 0;
        g[l = 1] = j - 1, g[len = 2] = j;
        fo(i, j + 1, n)
        {
            while (l < len && left(g[l], g[l + 1], j - 1) > right(g[l], g[l + 1]) * a[i]) l++;
            f[i][j] = f[g[l]][j - 1] + sqr(a[i] - a[g[l] + 1]);
            while (l < len && left(g[len - 1], g[len], j - 1) * right(g[len], i) >= left(g[len], i, j - 1) * right(g[len - 1], g[len])) len--;
            g[++len] = i;
        }
    }
    printf("%d\n", f[n][m]);
    return 0;
}

jzoj 2184. 羊羊列队

原文：https://www.cnblogs.com/jz929/p/11297133.html