记录编号	584549	评测结果	AAAAAAAAAA
题目名称	488.奇怪的监狱	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-11-13 16:19:41	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
int f[110][110],n,q,a[110];
void chu()
{
	for(int i=1;i<=q;i++)
	{
		f[i][i]=a[i+1]-a[i-1]-2;
	}
}
int main()
{
	freopen("prison.in","r",stdin);
    freopen("prison.out","w",stdout);
	memset(f,0x3f,sizeof(f));
	cin>>n>>q;
	for(int i=1;i<=q;i++)
	{
		cin>>a[i];
	}
	a[0]=0;
	a[q+1]=n+1;
	chu();
	for(int l=2;l<=q;l++)
	{
		for(int i=1;i<=q-l+1;i++)
		{
			for(int k=i;k<=i+l-1;k++)
			{
				int s=0;
				s+=a[i+l]-a[i-1]-2;
				if(k-1>=i)
				{
					s+=f[i][k-1];
				}
				if(k+1<=i+l-1)
				{
					s+=f[k+1][i+l-1];
				}
				f[i][i+l-1]=min(f[i][i+l-1],s);
			}
		}
	}
	cout<<f[1][q];
	return 0;
}