POJ 3184 Finicky Grazers

解法

Dはスペースの個数 / 牛の間隔の個数で求められる
Dの計算時の余りはD + 1にできる回数。問題に明記されてない気がするが、この回数分D + 1を使う必要がある

最小コストの計算はdpをする
dp[i][j] = 牛iを位置(i + D * i + j)に置いたときの最小コスト

そのままn * nの二重ループするとTLEするので、解になり得ない範囲は無視する

ソースコード

int main()
{
    int n, l;
    int x[ten(4)];
    scanf("%d%d", &n, &l);
    rep(i, n)
	scanf("%d", x + i);

    const int d = (l + 1 - n) / (n - 1);
    const int rem = (l + 1 - n) % (n - 1);

    const int inf = ten(8);
    int cur[ten(4) + 100], next[ten(4) + 100];
    fill_n(cur, rem + 1, inf);
    fill_n(next, rem + 1, inf);
    cur[0] = x[0];
    for (int i = 1; i < n; ++i)
    {
	const int lower = max(0, rem - (n - i));
	const int upper = min(i, rem);

	for (int j = lower; j <= upper + 1; ++j)
	    next[j] = inf;

	const int offset = (d + 1) * i;
	for (int j = lower; j <= upper; ++j)
	{
	    const int to = offset + j;
	    chmin(next[j], cur[j] + abs(x[i] - to));
	    chmin(next[j + 1], cur[j] + abs(x[i] - (to + 1)));
	}

	swap(cur, next);
    }
    printf("%d\n", cur[rem]);
}