比赛 20101101 评测结果 AAAAAAAAAA
题目名称 奇怪的监狱 最终得分 100
用户昵称 11111111 运行时间 0.019 s
代码语言 C++ 内存使用 4.11 MiB
提交时间 2012-11-05 11:22:48
显示代码纯文本
#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;
}