题解 | Grazing2-牛客假日团队赛9H题

* Line 1: Two space-separated integers: N and S
* Lines 2..N+1: Line i+1 contains the single integer: Pi

输出描述:

* Line 1: A single integer: the minimum total distance the cows have to travel. This number is guaranteed to be under 1,000,000,000 (thus fitting easily into a signed 32-bit integer).

示例1

5 10 
2 
8 
1 
3 
9 

4

Cows move from stall 2 to 3, 3 to 5, and 9 to 10. The total distance moved is 1 + 2 + 1 = 4. The final positions of the cows are in stalls 1, 3, 5, 8, and 10.
1 2 3 4 5 6 7 8 9 10
Init Stall | A | B | C | . | . | . | . | D | E | . |
Final Stall | A | . | B | . | C | . | . | D | . | E |
Distance moved | 0 | . | 1 | . | 2 | . | . | 0 | . | 1 |

解答

题目要求间距最大，那么我们显然好节点就一定在的位置，号节点就一定在最后

然后我们观察这个式子

不难发现最优情况下两个点的间距只可能是或者

而且的个数就是个

所以表示前个点有个是

注意第一个点就不做dp了，直接放到的位子

显然这个点的位置就是

那么我们到其位置的距离

答案

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int a[N],f[N][N],n,m,d;
int main()
{
    scanf("%d%d",&n,&m);m--;
    d=m/(n-1);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]--;
    sort(a+1,a+n+1);
    memset(f,63,sizeof f);
    f[1][0]=a[1];
    for(int i=2;i<=n;i++)
        for(int j=0;j<=min(i-1,m-d*(n-1));j++)
            f[i][j]=min(f[i-1][j],f[i-1][j-1])+abs(a[i]-((i-1)*d+j));
    printf("%d",f[n][m-d*(n-1)]);            
}