记录编号	38317	评测结果	AAAAAAAAAA
题目名称	[USACO Open09] 放牧2	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2012-04-17 11:39:51	内存使用	8.96 MiB

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1500 + 10, INF = ~0u>>2;
int n, m, s, t, a[N], f[N][N];
inline int get(int i, int j) {
    return t * (i-1) + j + 1;
}
int main() {
    freopen("graze2.in", "r", stdin);
    freopen("graze2.out", "w", stdout);
    scanf("%d %d", &n, &s);
    for(int i=1; i<=n; i++)
        scanf("%d\n", a+i);
    sort(a+1, a+n+1);
    m = (s-1) % (n-1), t = (s-1) / (n-1);
    for(int i=0; i<=n; i++) for(int j=0; j<=m; j++) f[i][j] = INF;
    f[1][0] = a[1] - 1;
    for(int i=2; i<=n; i++) {
        f[i][0] = f[i-1][0] + abs(get(i, 0) - a[i]);
        for(int j=1; j<=m && j<i; j++)
            f[i][j] = min(f[i-1][j-1], f[i-1][j]) + abs(get(i, j) - a[i]);
    }
    printf("%d\n",f[n][m]);
    return 0;
}