记录编号	50022	评测结果	AAAAAAAAAA
题目名称	奇怪的监狱	最终得分	100
用户昵称	日光。	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2012-11-10 20:24:07	内存使用	3.19 MiB

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;

int F[ 105 ][ 105 ];
int X[ 105 ];

int main()
{
	freopen("prison.in","r",stdin);
	freopen("prison.out","w",stdout);
	int P,Q;
	while ( cin >> P >> Q ) {
		for ( int i = 1 ; i <= Q ; ++ i )
			scanf("%d",&X[i]);
		X[0] = 0;X[Q+1] = P+1;
		
		for ( int i = 0 ; i <= Q+1 ; ++ i ) {
			for ( int j = i ; j <= Q+1 ; ++ j )
				F[i][j] = 100000;
			F[i][i+1] = 0;//X[i+1]-X[i]-1;
		}
		
		for ( int l =  2  ;  l  <= Q+1 ; ++ l )
		for ( int s =  0  ; s+l <= Q+1 ; ++ s )
		for ( int k = s+1 ;  k  <  s+l ; ++ k )
			if ( F[s][s+l] > F[s][k] + F[k][s+l] + X[s+l]-X[s]-2 )
				F[s][s+l] = F[s][k] + F[k][s+l] + X[s+l]-X[s]-2;

		printf("%d\n",F[0][Q+1]);
	}
	return 0;
}