题目描述

Farmer John has prize milk cows conveniently numbered 1..N. His newly-painted barn has stalls (conveniently numbered 1..S) in a single long line; each stall is a unit distance from its neighboring stall(s).
The cows have made their way to the stalls for a rest; cow i is in stall Pi. Antisocial as they are, the cows get grumpy if they are situated in stalls very close to each other, so Farmer John wants to move the cows to be as spread out as possible.
FJ wants to make sure that the N - 1 distances between adjacent cows are as large as possible, and he would also like them to be similar to each other (i.e., close to equi-distant spacing).
In particular, FJ would like all distances between adjacent cows to be at most 1 different from (S - 1) / (N - 1), where integer division is used. Moreover, he would like as many of these distances as possible to be exactly equal to (S - 1) / (N - 1) [integer division]. Thus, with four cows and eight stalls, one can place the cows at positions 1, 3, 5, 8 or 1, 3, 6, 8 but not at 1, 2, 4, 7 or 1, 2, 4, 8.
Help FJ spread the cows as efficiently as possible by calculating and reporting the minimum total distance that the cows have to move in order to achieve proper spacing. Ignore the distance it takes for a cow to enter or exit a stall.

输入描述:

* 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)]);            
}


来源：巨型方块