[JZOJ P1311] [DP]邮局设置问题

@kaike

传送门

学了DP我依旧一脸懵逼，这题大概和资源分配问题相似。枚举f[i][j]表示前i个有j个东西。

让求距离差，两个循环去枚举区间[i....j]的距离差。用w[i][j]表示区间[i....j]的距离差，

w[i][j]就是从前一个状态w[i][j-1]加上a[j]到中点的距离。

预处理也是DP。

把每个邮局放到每个村庄里的距离就是0.f[i][i]=0;当邮局小于村庄时就不要考虑这个问题辣。

前i个村庄里只有一个邮局的话，f[i][1]的值就和前i个村庄的距离差就相等；f[i][1]=w[1][i];

最终式子为：f[i][j]=min(f[i][j],f[k][j-1]+w[k+1][j]);（j-1<=k< i）

前i个村庄里j个邮局就是 前k个村庄里j-1个邮局加上[k+1....j]的村庄里只有1个邮局。

 

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int INF=999999;
int n,m,a[310],w[310][310],f[310][35];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            w[i][j]=w[i][j-1]+a[j]-a[(i+j)/2];
    for(int i=1;i<=n;i++)
    {
        f[i][i]=0;
        f[i][1]=w[1][i];
    }
    for(int j=2;j<=m;j++)
        for(int i=j+1;i<=n;i++)
        {
            f[i][j]=INF;
            for(int k=j-1;k<i;k++)
                f[i][j]=min(f[i][j],f[k][j-1]+w[k+1][i]);
        }
    cout<<f[n][m];
}