记录编号	48240	评测结果	AAAAAAAAAA
题目名称	488.奇怪的监狱	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2012-11-05 12:05:46	内存使用	6.83 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000 + 10, INF = 0x7fffffff;
int n, m, a[N];
int f[N][N];
bool v[N][N] = {0};
int DP(int l, int r) {
    if(l > r) return 0;
    if(v[l][r]) return f[l][r];
    v[l][r] = 1;
    int t = INF;
    for(int i=l; i<=r; i++)
        t = min(t, DP(l, i-1) + DP(i+1, r));
    return f[l][r] = (a[r+1] - 1) - (a[l-1] + 1) + t;
}
int main() {
    freopen("prison.in", "r", stdin);
    freopen("prison.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++)
        scanf("%d", a+i);
    a[0] = 0, a[m+1] = n + 1;
    sort(a, a+m+2);
    printf("%d\n", DP(1, m));
    return 0;
}