军训队列 | FFY's Blog

题意

>有 n 名学生参加军训，军训的一大重要内容就是走队列，而一个队列的不整齐程度是该队中最高的学生的身高与最矮的学生的身高差值的平方.现在要将 n 名参加军训的学生分成 k 个队列，每个队列的人数可以是任意非负整数。在安排队列时希望所有队列的不整齐度之和尽量小，请问不整齐度之和最小可以是多少？

• 排序
• DP

先将身高排序,问题就转换成将一个区间切成$k$段,求$k$个区间的极值差平方和的最小值
对于每一个人,他的决策无非两种,加到上一个区间,或者自立门户,状态转移方程:

1. 加入上一个区间:   $f[i][j][k]=min(f[i-1][j][k]-v[j][i-1]+v[j][i])$
2. 自立门户:              $f[i][i][k]=min(f[i-1][j][k-1])$

我们可以$n^2$预处理出v数组,时间复杂度为$(o)n^3$
但问题又来了,空间复杂度是$n^3+n^2$,可能开不下
我们观察到$i$维每次有用的状态只有两位,我们可以用一个滚动数组优化空间,空间复杂度变为$3\times n^2$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=510;
int n,m,h[maxn],cnt;
int f[2][maxn][maxn];
int v[maxn][maxn];
int main()
{
    freopen("queue.in","r",stdin);
    freopen("queue.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    if(n==m)
    {
        printf("0\n");
        return 0;
    }
    sort(h+1,h+1+n);memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)
    v[i][j]=(h[j]-h[i])*(h[j]-h[i]);
    f[0][0][0]=0;
    for(int i=1;i<=n;i++)
    {
        cnt^=1;memset(f[cnt],0x3f,sizeof f[cnt]);
        for(int j=0;j<i;j++)
        {
            for(int k=1;k<=m;k++)
            {
                f[cnt][i][k]=min(f[cnt][i][k],f[cnt^1][j][k-1]);
                f[cnt][j][k]=min(f[cnt][j][k],f[cnt^1][j][k]-v[j][i-1]+v[j][i]);
            }
        }
    }
    int ans=1e9+7;
    for(int i=1;i<=n;i++)
    ans=min(ans,f[cnt][i][m]);
    printf("%d\n",ans);
    return 0;
}