记录编号	49760	评测结果	AAAAAAAAAA
题目名称	奇怪的监狱	最终得分	100
用户昵称	11111111	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2012-11-09 08:34:08	内存使用	1.27 MiB

#include<fstream>
using namespace std;
int n,g,temp,i,j,k;
int l[500],t[501];
int f[500][500]={0};
int minn(int x,int y)
{
	if (x<y) return x; else return y;
}
int main()
{
	ifstream fin("prison.in");
	ofstream fout("prison.out");
	fin>>n>>g;
	for (i=1;i<=g;i++)
		fin>>l[i];
	for (i=1;i<=g;i++)
		for (j=1;j<=g;j++)
			if (l[i]<l[j]) 
			{
				temp=l[i];
				l[i]=l[j];
				l[j]=temp;
			}
	for (i=1;i<=g;i++)
		t[i]=l[i]-l[i-1]-1;
	t[g+1]=n-l[g];
	for (i=1;i<=g+1;i++)
		for (j=1;j<=g+1;j++)
			f[i][j]=100000000;
	for (i=1;i<=g+1;i++)
	{
		t[i]=t[i]+t[i-1];
		f[i][i]=0;
	}
	for (i=g;i>=1;i--)
		for (j=1+i;j<=g+1;j++)
			for (k=i;k<=j-1;k++)
				f[i][j]=minn(f[i][j],f[i][k]+f[k+1][j]+(t[j]-t[i-1])+(j-i-1));
	fout<<f[1][g+1];
	fin.close();
	fout.close();
	return 0;
}