记录编号	49409	评测结果	AAAAAAAAAA
题目名称	奇怪的监狱	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2012-11-07 20:33:53	内存使用	3.36 MiB

//date 20120116
//creater cyr
//way dp
#include <fstream>
using namespace std;
ifstream cin("prison.in");
ofstream cout("prison.out");
int p,q,b[101],a[101],f[101][101],t[101][101];
void init()
{
	int i,j,o;
	cin>>p>>q;
	for (i=1;i<=q;i++) cin>>b[i];
	for (i=1;i<=q-1;i++)
		for (j=i+1;j<=q;j++)
			if (b[j]<b[i]) {o=b[j];b[j]=b[i];b[i]=o;}
	a[1]=b[1]-1;
	for (i=2;i<=q;i++)
		a[i]=b[i]-b[i-1]-1;
	a[q+1]=p-b[q];
	for (i=1;i<=q+1;i++)
	{
		f[i][i]=0;
		for (j=1;j<=q+1;j++) t[i][j]=0;
	}
	for (i=1;i<=q+1;i++)
		for (j=1;j<=q+1;j++)
			for (o=i;o<=j;o++) t[i][j]+=a[o];
}
int main()
{
	int i,j,k,l,ans,ans1;
	init();
	for (k=1;k<=q;k++)
	{
		for (i=1;i<=q-k+1;i++)
		{
			j=i+k;
			ans=f[i+1][j]+t[i][j]+j-i-1;
			for (l=i+1;l<=j-2;l++)
			{
				ans1=f[i][l]+f[l+1][j]+t[i][j]+j-i-1;
				if (ans1<ans) ans=ans1;
			}
			ans1=f[i][j-1]+t[i][j]+j-i-1;
			if (ans1<ans) ans=ans1;
			f[i][j]=ans;
		}
	}
	cout<<f[1][q+1]<<endl;
	return 0;
}