记录编号	52761	评测结果	AAAAAAAAAA
题目名称	858.磁性链	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2013-02-15 13:40:41	内存使用	2.00 MiB

#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("linka.in");
ofstream fout("linka.out");
int N,Q,f[200][200],Len[200][2000],A[2000];
void Initialize()
{
int i,j;
	fin>>N>>Q;
	Q++;
	A[Q]=N+1;
	for(i=1;i<=Q;i++)
	{
		fin>>A[i];
		Len[i][i]=A[i]-A[i-1]-1;
	}
	for(i=2;i<=Q;i++)
		for(j=1;j+i-1<=Q;j++)
			Len[j][j+i-1]=Len[j][j]+Len[j+1][j+i-1]+1;
}
void Dp()
{
int i,j,len,k;
	for(len=2;len<=Q;len++)
		for(i=1;i+len-1<=Q;i++)
		{
		int Min=123456789;
			j=i+len-1;
			for(k=i;k<j;k++)
				Min=min(Min,f[i][k]+f[k+1][j]+Len[i][k]+Len[k+1][j]);
			f[i][j]=Min;
		}
	fout<<f[1][Q]<<endl;
}
int main()
{
	Initialize();
	
	Dp();
	
	fin.close();
	fout.close();
	return 0;
}