记录编号	21426	评测结果	AAAAAAAAAA
题目名称	488.奇怪的监狱	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C	运行时间	3.015 s
提交时间	2010-11-10 16:15:24	内存使用	3.99 MiB

#include <stdio.h>

int main(void)
{
	int p,q,list[1001],i,j,k,l,f[1001][1001]={{0}};
	FILE *f1=fopen("prison.in","r");
	FILE *f2=fopen("prison.out","w");

	fscanf(f1,"%d %d\n",&p,&q);
	for (i=0; i<q; i++)
	{
		fscanf(f1,"%d ",&list[i]);
        f[list[i]][list[i]+1]=1;
        f[list[i]-1][list[i]]=1;
	}

	for (k=2; k<p; k++)
		for (i=1; i+k<=p; i++)
		{
			j=i+k;

			for (l=0; l<q; l++)
				if (list[l]>=i && list[l]<=j)
				{
					if (f[i][list[l]-1]+f[list[l]+1][j]+j-i<f[i][j] || !f[i][j])
						f[i][j]=f[i][list[l]-1]+f[list[l]+1][j]+j-i;
				}
		}

	fprintf(f2,"%d\n",f[1][p]);

    fclose(f1);
    fclose(f2);

	return 0;
}