WORLDCREATER

/*
ID: roselone
LANG: C++
TASK: barn1
*/

//动态规划求解,
//将有牛的牛棚排序后,设置一个函数d[i,j]表示第i个牛修到第j个牛需要使用的木版长度,设f[i,j]表示用前i个木版修到第j头牛所用的最短长度.
//f[i,j]=min{f[i-1,k]+d[k,j]}; (i<=k<=j)
#include<iostream>
#include<fstream>
#include<string>
#include<algorithm>

using namespace std;
int d[201][201];
int f[51][201];
int m,s,c;
int a[51];
ifstream fin("castle.txt");
ofstream fout("barn1.out");
bool cmp(int a,int b)
{
        return (a<b);
}

void init()
{
        fin>>m>>s>>c;
        for (int i=1;i<=c;i++)
                fin>>a[i];
        sort(a+1,a+c+1,cmp);
        for (int i=1;i<=c;i++)
        {       d[i][i]=1;
        f[i][i]=i;}
        for (int i=1;i<=c;i++)
                {f[1][i]=a[i]-a[1]+1; }
        for (int i=1;i<c;i++)
                for (int j=i+1;j<=c;j++)
                        d[i][j]=a[j]-a[i]+1;
}

int main()
{
        init();
        for (int i=2;i<=m;i++)
                for (int j=i;j<=c;j++)
                {  f[i][j]=220;
                        for (int k=i;k<=j;k++)
                        {
                                int temp=f[i-1][k-1]+d[k][j];
                                if (temp<f[i][j]) f[i][j]=temp;
                        }
                }
        if (m>=c) fout<<c<<endl;
        else
        cout<<f[m][c]<<endl;                               
        return 0;
}