[USACO 2009 Ope S]Grazing2

NC24878. [USACO 2009 Ope S]Grazing2

描述

Farmer John has N (2 <= N <= 1,500) prize milk cows conveniently numbered 1..N. His newly-painted barn has S (N <= S <= 1,000,000) 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

输入:

输出:

说明:

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 |

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 15ms, 内存消耗: 12380K, 提交时间: 2019-08-05 18:40:21

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int num[1750],dp[1750][1750],n,s,d;
int main(){
	while(cin>>n>>s){
		for(int i=1;i<=n;i++)	cin>>num[i];
		d=(s-1)/(n-1);
		sort(num+1,num+1+n);
		for(int i=0;i<1750;i++){
			for(int j=0;j<1750;j++){
				dp[i][j]=1e7;
			}
		}
		dp[1][1]=num[1]-1;
		for(int i=2;i<=n;i++){
			for(int j=1;j<=i&&j<=s-(n-1)*d;j++){
				dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+abs(num[i]-(i-1)*d-j);
			}
		}
		cout<<dp[n][s-(n-1)*d];
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 14ms, 内存消耗: 16200K, 提交时间: 2019-08-16 16:47:43

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