军训队列–常规DP or 斜率优化DP

题意

把 $n$ 个数的排列，可以更换顺序，分成 $k$ 段，每段的花费为段内极差的平方（最大值减最小值的平方），要让消费总和尽可能小。所有的元素不超过 $200$ 。

很显然需要先把他按照从小到大排序，然后这样分段之内可以得到尽可能小的极差平方会是最小的。接下来我们以数组已经按从小到大排序为前提来继续推算。

常规DP

接下来就设 $dp[n][k]$ 为排序之后，前 $n$ 个分成 $k$ 列之后的最小消费

显然有

$$ dp[i][k]=\min_{j=1}^{i-1} (dp[j][k-1]+(a[i]-a[j+1])^2) $$

显然有 $dp[i][1]=(a[i]-a[1])^2$ 的初始状态，就可以做状态转移了。

这个复杂度为 $O(n^2 k)$ 虽然本题 $n,k$ 上限都是 $500$ ，但是还要带上一个 $\dfrac{1}{2}$ ，所以实际运算量级不超过 $10^8$ 。1秒的运算量约为 $3\times 10^8$ ，所以肯定是能过的。

const int maxn = 510;
int n, k;
int a[maxn];
int dp[maxn][maxn];
int main()
{
    n = rd(), k = rd();
    for (int i = 1; i <= n; ++i)
        a[i] = rd();
    std::sort(a + 1, a + n + 1);
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; ++i)
        dp[i][1] = (a[i] - a[1]) * (a[i] - a[1]);
    for (int loop = 2; loop <= k; ++loop)
        for (int cur = 1; cur <= n; ++cur)
            for (int pre = 1; pre < cur; ++pre)
                dp[cur][loop] = min(dp[cur][loop], dp[pre][loop - 1] + (a[cur] - a[pre + 1]) * (a[cur] - a[pre + 1]));
    wr(dp[n][k]);
}

但是一旦 $n$ 变大了，就不行了。所以我们引入下面的斜率优化做法。

斜率优化DP

这个东西网上能查到的也很多了，基本上就是在已知 $dp[i]=\min_{j=1}^{i-1} f(dp[j])$ 的类似形式，且后面的状态转移方程同时与 $i,j$ 相关时所采用的优化策略，本质上是通过将已知状态转换为二维坐标图，利用其凸壳的单调性优化运算速度。

我们来重新拆解一下上面的方程，将只与 $i$ 有关的，只与 $j$ 有关的，与 $i,j$ 均有关的项分别拆分出来：

$$ dp[i][k]-a[i]^2=dp[j][k-1]+a[j+1]^2 - 2a[i]a[j+1]\quad (1\le j\le i-1) $$

然后我们将这个式子写为 $b=y-kx$ 的形式，将与 $i,j$ 相关的那一项与 $j$ 相关的部分当做横坐标，与 $i$ 相关的部分当做斜率，只与 $j$ 相关的部分当做纵坐标，只与 $i$ 相关的部分当做截距，就有：

• $b=dp[i][k]-a[i]^2$
• $x_j = a[j+1]$
• $y_j = dp[j][k-1]+a[j+1]^2$
• $k=2a[i]$

而我们要维护的是最小值，那么实际上就是将所有的点组成下凸壳，斜率恰好大于 $2a[i]$ 且最小的那条直线与下凸壳相切，其切点即为我们所需要的决策点。

在数组从小到大排序之后，很显然插入点集的 $x_j$ 递增，查询的斜率 $k$ 递增，所以我们使用单调队列进行维护即可。跑一轮的时间复杂度是 $O(n)$ 的。需要注意的是，如果插入点集或者查询的斜率不单调递增，两者每有一个不递增，复杂度就要多一个 $\log$ 。具体做法包括在单调队列上二分查找，利用平衡树/李超线段树维护凸壳等，具体不再在这里赘述。

然后跑 $k$ 轮的斜率优化DP就可以了。由于 $k$ 的状态只由 $k-1$ 而来，所以针对这个维度我们还可以做降维优化。

总时间复杂度 $O(nk)$ ，空间复杂度 $O(n)$ 。

const int maxn = 510;
int n, k;
int a[maxn];
int dp[2][maxn], cur, pre;
i64 X(int idx) { return a[idx + 1]; }
i64 Y(int idx) { return dp[pre][idx] + a[idx + 1] * a[idx + 1]; }
// > k return 1, == k return 0, < k return -1
int judge_slope_real(int i, int j, i64 k)
{
    i64 flag = (Y(j) - Y(i)) - k * (X(j) - X(i));
    return flag > 0 ? 1 : flag == 0 ? 0 : -1;
}
// judge slope(i, j) slope(i, k)
int judge_slope_index(int i, int j, int k)
{
    i64 flag = (Y(j) - Y(i)) * (X(k) - X(i)) - (Y(k) - Y(i)) * (X(j) - X(i));
    return flag > 0 ? 1 : flag == 0 ? 0 : -1;
}
struct monotone_queue_convex
{
    int flag; // flag = -1 : down, flag = 1 : up
    std::deque<int> q;
    monotone_queue_convex(int _flag = -1) : flag(_flag) {}
    void pop_back_by_slope(i64 k)
    {
        while (q.size() >= 2 && judge_slope_real(q.back(), q[q.size() - 2], k) * flag >= 0)
            q.pop_back();
    }
    void push_front_by_convex(int x)
    {
        while (q.size() >= 2 && judge_slope_index(q[1], q.front(), x) * flag <= 0)
            q.pop_front();
        q.push_front(x);
    }
};
int main()
{
    n = rd(), k = rd();
    for (int i = 1; i <= n; ++i)
        a[i] = rd();
    std::sort(a + 1, a + n + 1);
    pre = 0, cur = 1;
    for (int i = 1; i <= n; ++i)
        dp[pre][i] = (a[i] - a[1]) * (a[i] - a[1]);

    for (int loop = 2; loop <= k; ++loop)
    {
        monotone_queue_convex slope_queue(-1);
        slope_queue.push_front_by_convex(loop - 1);
        for (int i = loop; i <= n; ++i)
        {
            slope_queue.pop_back_by_slope(2 * a[i]);
            int j = slope_queue.q.back();
            dp[cur][i] = dp[pre][j] + (a[i] - a[j + 1]) * (a[i] - a[j + 1]);
            slope_queue.push_front_by_convex(i);
        }
        cur = 1 - cur, pre = 1 - pre;
    }
    wr(dp[pre][n]);
}