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

#include<bits/stdc++.h>
    using namespace std;
    int n,m,s,k,op,f[1010][1010],a[1010],b[1010];//f[i][j]表示放第i个到第j个最小花费（i<=j<=m） 
    int main(){
        freopen("prison.in","r",stdin);
        freopen("prison.out","w",stdout);
          cin>>n>>m;
          for(int i=1;i<=m;i++){
              cin>>a[i];
          }
          sort(a+1,a+1+m);
          a[m+1]=n+1;//到边界 
          memset(f,0x3f,sizeof(f));
          for(int i=1;i<=m;i++){
              f[i][i]=a[i+1]-a[i-1]-2;//初始最小即它是最后一个放的 
          }//f[i][i]推到f[1][m] 
          for(int l=2;l<=m;l++){
              for(int j=1;j+l-1<=m;j++){
                  for(int k=j;k<=l+j-1;k++){
                      int op=0;
                      op+=a[j+l]-a[j-1]-2;//第一个释放的总要花费的数额 
                      if(k-1>=j){
                          op+=f[j][k-1];
                      }
                      if(l+j-1>=k+1){
                          op+=f[k+1][l+j-1];
                      }
                      f[j][j+l-1]=min(f[j][j+l-1],op);
                      
                  }
              }
          }
          cout<<f[1][m];
    }