P2954 【[USACO09OPEN] 移动牛棚 Grazing2】

Rainbow_qwq · 2019-08-30 12:00:40 · 题解

[USACO09OPEN]移动牛棚Grazing2

思路

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

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

解得\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))}。

转移方程：

边界条件：第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;
}