题解——修理牛棚

解题思路：

此题意思为：给定木板的数量和牛棚的序号，将牛棚用木板连接起来，求出木板的总长度的最小值。

比如：

1个木板，5个牛棚分别为$3、5、8、10、11$

则用两个木板连接5个牛棚，最短解法是 $3、4 、8、10、11$ ，总长度为 $9$，即$ 11 - 3 + 1$；

再比如：

2个木板，5个牛棚分别为$3、5、8、10、11$

多出来一条木板，我们肯定想把间距最小的几个连在一起，我们先求出每个木板之间的间隔为$2、3、2、1$；

显然编号5和8之间间隔3，间隔最大，故将3去除，即$ 9 - 3 + 1 = 7$；

故最短解法是 $3、5 、8、10、11$ ，总长度为 7 ，第一块木板$（4-3+1）=3$，第二块木板长$（11-8+1）= 4$；

解题步骤：

所以本题首先要将木板按编号排序，再求出所有的木板之间的间距，将间距也排序，

先假设有一块木板，再减去最大的间距，减去次大的间距，……，直到达到最大木板数。

最后比如：

3个木板，5个牛棚分别为$2、4、6、8、7$

1.木板排序：$[2,4,6,7,8]$
2.求间距：$[2,2,1,1]$
3.间距排序：$[2,2,1,1]$
4.假设只有一块木板，总长 8-2+1=7；
5.有两块木板，减去最大间隔，总长 $7-2+1=6$；
6.有三块木板，减去次大间隔，总长 $6-2+1=5$；

来，上食用方法

#include<bits/stdc++.h>//万能头文件
using namespace std;//命名空间
int f[1314],a[1314],n,k,m;//定义
int main(){
    scanf("%d%d%d",&m,&k,&n);
    if(m>=n)//可以先特判，木板数>=牛棚数，直接就输出牛棚数
    {
        printf("%d\n",n);
        return 0;
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);//对牛棚位置进行排序
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=1;j--)//从大到小
            f[j]=min(f[j]+a[i]-a[i-1],f[j-1]+1);
        f[0]=1<<30;
        //注意！由于f[0]不参与计算，所以如果没有把它在每一个阶段后赋值为很大的数，结果必然是1
    }
    printf("%d\n",f[m]);
    //最后一定要输出f[m]，因为无论怎样，木板数越多，需要盖住的和就肯定会少。不能在f[1]~f[m]中取最小值
    return 0;
}