luogu_P4677 山区建小学

传送门：https://www.luogu.org/problem/P4677

听说这题LYH只用了2分钟就A了，ttql

发现只有一个学校那么就是找中位数，多个学校呢？

我不知道在哪里建小学啊，mmp，dp枚举小学范围的分界点。（我是这么理解的

所以f[i][j]表示i~j建一个学校的最小花费，就找中位数对吧。

然后dp[i][j]表示前i个村建j个学校的最小花费, 转移方程 dp[i][j]=min{dp[k][j-1]+f[k+1][i]}.

#include<cstdio>
#define R register
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,s[510];
int f[510][510];
int dp[510][510];
int main (){
    scanf("%d%d",&n,&m);
    for(R int i=2;i<=n;i++){
        scanf("%d",&s[i]);
        s[i]+=s[i-1];
    }
    for(R int i=1;i<=n;i++){
        for(R int j=i;j<=n;j++){
            int mid=(i+j)>>1;
            for(R int k=i;k<=j;k++) f[i][j]+=abs(s[mid]-s[k]);
        }
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(R int i=1;i<=n;i++){
        for(R int j=1;j<=m;j++){
            if(j>=i){
                dp[i][j]=0;
                continue;
            }
            for(R int k=j-1;k<=i;k++){
                dp[i][j]=min(dp[i][j],dp[k][j-1]+f[k+1][i]);
            }
        }
    }
    printf("%d\n",dp[n][m]);
    return 0;
}

View Code