比赛 20101101 评测结果 C
题目名称 奇怪的监狱 最终得分 0
用户昵称 feng 运行时间 0.000 s
代码语言 C 内存使用 0.00 MiB
提交时间 2012-11-05 08:27:05
显示代码纯文本
#include<fstream>
using namespace std;
int n,q,t,i,j,k;
int a[500],s[500];
int f[500][500];
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>>q;
	for (i=1;i<=q;i++)
		fin>>a[i];
	for (i=1;i<=q;i++)
		for (j=1;j<=q;j++)
			if (a[i]<a[j]) 
			{
				t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
	for (i=1;i<=q;i++)
		s[i]=a[i]-a[i-1]-1;
	s[q+1]=n-a[q];
	for (i=1;i<=q+1;i++)
		s[i]=s[i]+s[i-1];
	for (i=1;i<=q+1;i++)
		for (j=1;j<=q+1;j++)
			f[i][j]=100000000;
	for (i=1;i<=q+1;i++)
		f[i][i]=0;
	for (i=q;i>=1;i--)
		for (j=1+i;j<=q+1;j++)
			for (k=i;k<=j-1;k++)
				f[i][j]=minn(f[i][j],f[i][k]+f[k+1][j]+(s[j]-s[i-1])+(j-i-1));
	fout<<f[1][q+1];
	fin.close();
	fout.close();
	return 0;
}