Luogu P4677 山区建小学

Author： YorkWu
发布时间：April 21, 2019
1151 views
No comments
524 words
Categories： OI 题目

[题目链接](https://www.luogu.org/problemnew/show/P4677 "题目链接")

* * *

这题做了一个小时，最后还是借鉴了题解······ 这题得开俩数组，$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)$(直觉我没有)

* * *

代码如下：
```cpp
    #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 14, 2020