比赛 NOIP2023模拟赛1 评测结果 AAAAAAAAAA
题目名称 奇怪的监狱 最终得分 100
用户昵称 Murasame 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2023-11-13 12:30:01
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int p,q;
int a[110],pre[110],dp[110][110];
int main(){
	freopen("prison.in","r",stdin);
	freopen("prison.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>p>>q;
	for(int i=1;i<=q;i++){
		cin>>a[i];
	}
	a[q+1]=p+1;
	for(int i=1;i<=q;i++){
		for(int j=1;j+i<=q+1;j++){
			dp[j][j+i-1]=0x3f3f3f3f;
			for(int k=j;k+1<=i+j;k++){
				dp[j][j+i-1]=min(dp[j][j+i-1],dp[j][k-1]+dp[k+1][j+i-1]+a[j+i]-a[j-1]-2);
			}
		}
	}
	cout<<dp[1][q]<<endl;
	return 0;
}