记录编号	584255	评测结果	AAAAAAAAAA
题目名称	[POI 1999] 地图着色	最终得分	100
用户昵称	宇战	是否通过	通过
代码语言	C++	运行时间	0.134 s
提交时间	2023-11-04 17:30:02	内存使用	4.05 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,s,a[1000000],b[1000000];
int dp[3010][11];
int fi(int x,int y){
    int mid=a[(x+y)>>1],i=x+y>>1;
    int s=mid*(i-x+1)-(b[i]-b[x-1])+b[y]-b[i]-mid*(y-i);
    return s;
}
int main(){
    freopen("map.in","r",stdin);
    freopen("map.out","w",stdout);
      cin>>n>>m;
      memset(dp,0x3f,sizeof(dp));
      for(int i=1;i<=n;i++){                  
          cin>>a[i];          
            
      }
      sort(a+1,a+1+n);
      for(int i=1;i<=n;i++){
          b[i]=b[i-1]+a[i];  
          dp[i][1]=fi(1,i);
      }
      for(int k=2;k<=m;k++){
          for(int i=1;i<=n;i++){
              for(int j=1;j<i;j++){
                  dp[i][k]=min(dp[j][k-1]+fi(j+1,i),dp[i][k]);
              }
          }
      }
      cout<<dp[n][m];
      return 0;
}