自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 21:43:48，当前版本为作者最后更新于2019-08-30 12:00:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[USACO09OPEN]移动牛棚Grazing2

思路

$dp$

先对牛排一遍序。
手推一下数据，发现对于每一头牛，它的距前一头牛的距离都是$d$或$d+1$。

有$n-1$个间隔，设有$c_1$个间隔为$n$,$c_2$个间隔为$n+1$，可列方程：

$\begin{cases} \mathrm{c_1+c_2=n-1} \\ \mathrm{c_1\times d+c_2\times (d+1)=s}\end{cases}$

解得$\mathrm{c_2=s-(n-1)\times d}$

然后设计$dp$状态，设$\mathrm{f[i][j]}$表示前$i$头牛，$j$个间隔为$n+1$的最小值。

答案即为$\mathrm{f[n][c_2]}$。

接下来是状态转移方程：对于这一个间隔，可以选$n$，也可以选$n+1$。

如果选了$j$个区间长度$n+1$,就有$i-j-1$个区间长度$n$。那这个点的“坐标”就是$\mathrm{(i-j-1)\times n+j\times(n+1)}$,简化可得$\mathrm{d\times (i-1)+j}$
与第$i$头牛的距离就是$\mathrm{abs(a[i]-(d\times (i-1)+j))}$。

转移方程： $\mathrm{f[i][j]=min(f[i-1][j],f[i-1][j-1])+abs(a[i]-(d\times (i-1)+j))}$

边界条件：第1头牛调整到1位置，$\mathrm{f[1][1]=a[1]-1}$

时间复杂度：2重循环，$O(n*s)$

代码：

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
int n,s,d,c2,f[1509][1509];
int a[1509];
int main()
{
    memset(f,63,sizeof f);
    n=read(),s=read(),d=int((s-1)/(n-1));c2=s-(n-1)*d;
    //预处理出s,c2的值
    For(i,1,n)a[i]=read();
    sort(a+1,a+n+1);//排一遍序
    f[1][1]=a[1]-1;//边界条件
    For(i,2,n)//dp
        For(j,1,min(c2,i))
            f[i][j]=min(f[i-1][j],f[i-1][j-1])+abs(a[i]-(d*(i-1)+j));
    cout<<f[n][c2];
    return 0;
}