题目链接


这题做了一个小时,最后还是借鉴了题解······ 这题得开俩数组,$f\[i\]\[j\]$记录从i到j建一所学校的最小距离,然后$dp\[i\]\[j\]$就是前i个里面建j所学校的最小距离,状态转移方程: $dp\[i\]\[j\]=min(dp\[i\]\[j\],dp\[k\]\[j-1\]+f\[k+1\]\[i\])$ 然后$f\[i\]\[j\]=dis(k,mid)$(直觉我没有)


代码如下:

    #include<bits/stdc++.h>
    using namespace std;

    int n,m,in[509],f[509][509],dp[509][509],a[509];

    int main(){
        cin>>n>>m;
        for(int i=1;i<n;i++){
            cin>>in[i];a[i+1]=a[i]+in[i];
        }
        for(int k=1;k<n;k++){
            for(int l=1;l+k<=n;l++){
                int r=l+k;
                int mid=(l+r)/2;
                for(int p=l;p<=r;p++) f[l][r]+=abs(a[mid]-a[p]);
            }
        }
        memset(dp,0x3f,sizeof(dp));
        dp[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(j>i) {
                    dp[i][j]=0;
                    continue;
                }
                for(int k=j-1;k<=i;k++){
                    dp[i][j]=min(dp[i][j],dp[k][j-1]+f[k+1][i]);
                }
            }
        }
        cout<<dp[n][m];
        return 0;
    }
Last modification:March 14th, 2020 at 08:45 pm