记录编号	167214	评测结果	AAAAAAAAAA
题目名称	磁性链	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2015-06-22 16:36:00	内存使用	4.19 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
 
#define MAXN 1010
 
#define Min(a,b) ((a)<(b)?(a):(b))
 
using namespace std;
 
int n,q;
int fee[MAXN];
int sum[MAXN];
int f[MAXN][MAXN];
 
int main(){
     
    /*1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20*/
     
    /*3 6 14*/
     
    /*区间动规*/
    freopen("linka.in","r",stdin);
	freopen("linka.out","w",stdout); 
    int i,j,l;
     
    scanf("%d%d",&n,&q);
     
    for(i=0;i<=n;++i)
    	for(j=0;j<=n;++j)
    		f[i][j]=0x3fffffff;
             
    for(i=1;i<=q;++i)
        scanf("%d",&fee[i]);
         
    sort(fee+1,fee+q+1);
     
    for(i=1;i<=q;++i){
        f[i][i]=0;
        sum[i]=sum[i-1]+(fee[i]-fee[i-1]-1);//区间两端的差值再减1才是包含人数
    }
     
    /*DP*/
     
    f[q+1][q+1]=0;
    sum[q+1]=sum[q]+n-fee[q];
    q=q+1;
     
    for(l=1;l<q;++l)
        for(i=1;i+l<=q;++i)
            for(j=i;j<i+l;++j){
                f[i][i+l]=Min(f[i][i+l],f[i][j]+f[j+1][i+l]+sum[i+l]-sum[i-1]+l-1);
                //printf("f[%d][%d]=%d\n",i,i+l,f[i][i+l]);
         	}
    printf("%d",f[1][q]);
     
}