【题解】P6173 [USACO16FEB] Circular Barn P

· · 题解

题意

有顺时针编号的 n 个房间，房间 i 有 r_i 头奶牛，你需要在这些房间中开 k 扇门，每个奶牛会从某个门进入，然后顺时针行走到自己的谷仓，求奶牛行走距离总和的最小值。

思路

在一个环上比较难考虑，因此我们断环为链，这里需要 O(n) 的时间复杂度。

设 dp_{i,j} 为前 i 个房间开 j 扇门时奶牛行走距离的总和，则有转移方程如下：

dp_{i,j}=\min_{k=0}^{i-1}dp_{k,j-1}+w(k+1,i)

其中 w(i,j) 为在房间 i 开门，房间编号为 i\sim j 的奶牛的行走距离总和，可以 O(n^2) 预处理出来。

这个做法是 O(n^3k) 的，无法通过此题，但是可以通过此题的弱化版。

通过打表可以发现对于 a\le b\le c\le d 有 w(a,c)+w(b,d)\le w(a,d)+w(b,c)，证明如下：

w(a,c)=r_{a+1}+2r_{a+2}+\dots+(c-a)a_c\\ w(a,d)=r_{a+1}+2r_{a+2}+\dots+(d-a)a_d\\ w(a,d)-w(a,c)=(c+1-a)a_{c+1}+(c+2-a)a_{c+2}+\dots+(d-a)a_d\\ w(b,d)=r_{b+1}+2r_{b+2}+\dots+(d-b)a_d\\ w(b,c)=r_{b+1}+2r_{b+2}+\dots+(c-b)a_c\\ w(b,c)-w(b,d)=-(c+1-b)a_{c+1}-(c+2-b)a_{c+2}-\dots-(d-b)a_d\\ w(a,d)+w(b,c)-w(a,c)-w(b,d)=(b-a)a_{c+1}+(b-a)a_{c+2}+\dots+(b-a)a_d\\ w(a,d)+w(b,c)-w(a,c)-w(b,d)\ge0\\ w(a,c)+w(b,d)\le w(a,d)+w(b,c)

满足四边形不等式，故满足决策单调性，考虑使用分治优化，最终时间复杂度为 O(n^2k\log n)，可以通过此题。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5,M=15,inf=(int)4e18+5;
int a[N<<1],w[N<<1][N<<1],dp[N][M];
void solve(int bgn,int id,int l,int r,int lpt,int rpt)
{
    if(l>r)return;
    int mid=l+r>>1,opt;
    for(int i=lpt;i<=min(mid,rpt);i++)
    {
        int val=dp[i][id-1]+w[i+bgn][mid+bgn-1];
        if(dp[mid][id]>val)dp[mid][id]=val,opt=i;
    }
    solve(bgn,id,l,mid-1,lpt,opt),solve(bgn,id,mid+1,r,opt,rpt);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],a[i+n]=a[i];
    for(int i=1;i<=(n<<1);i++)
    for(int j=i+1;j<=(n<<1);j++)
        w[i][j]=w[i][j-1]+a[j]*(j-i);
    int ans=inf;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<N;j++)
        for(int k=0;k<M;k++)
            dp[j][k]=inf;
        for(int j=1;j<=m;j++)solve(i,j,0,n,0,n);
        ans=min(ans,dp[n][m]);
    }
    cout<<ans;
    return 0;
}