比赛 动态规划练习赛1102 评测结果 MMMMMMMMMM
题目名称 地图着色 最终得分 0
用户昵称 小金 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2023-11-02 21:59:18
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long f[3010][3010][11],a[3010];
int n,m;
long long qp(int l,int r)
{
    long long s=0,p;
    if((r-l+1)^1)
    {
        int mid=(l+r)/2;
        p=a[mid];
    }
    else
    {
        int mid=(l+r)/2;
        p=(a[mid]+a[mid+1])/2;
    }
    for(int i=l;i<=r;i++)
    {
        s+=abs(a[i]-p);
    }
    return s;
}
int main()
{
    freopen("map.in","r",stdin);
    freopen("map.out","w",stdout);
    memset(f,0x3f,sizeof(f));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            f[i][j][1]=qp(i,j);
            //cout<<i<<' '<<j<<' '<<f[i][j][1]<<endl;
        }
    }
    for(int x=2;x<=m;x++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                for(int k=i;k<j;k++)
                {
                    f[i][j][x]=min(f[i][j][x],f[i][k][x-1]+f[k+1][j][x-1]);
                }
            }
        }
    }
    cout<<f[1][n][m];
    return 0;
}