记录编号	39335	评测结果	AAAAAAAAAA
题目名称	磁性链	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.029 s
提交时间	2012-07-09 13:21:50	内存使用	4.19 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000 + 10;
int n, m, q, a[N], s[N], f[N][N];
int main() {
    freopen("linka.in", "r", stdin);
    freopen("linka.out", "w", stdout);
    scanf("%d %d", &n, &q);
    m = q + 1;
    for(int i=1; i<=q; i++)
        scanf("%d", a+i);
    sort(a+1, a+m);
    for(int i=1; i<=q; i++)
        s[i] = a[i] - a[i-1] - 1;
    s[m] = n - a[q];
    for(int i=1; i<=m; i++)
        s[i] += s[i-1];
    memset(f, 4, sizeof(f));
    for(int i=1; i<=m; i++)
        f[i][i] = 0;
    for(int i=m; i>0; i--)
        for(int j=i+1; j<=m; j++)
            for(int k=i; k<j; k++)
                f[i][j] = min(f[i][j], f[i][k]+f[k+1][j] + s[j]-s[i-1] + j-i-1);
    printf("%d\n", f[1][m]);
    return 0;
}