P3080 [USACO13MAR]The Cow Run G/S题解

· · 题解

区间 dp。

设 f_{i,j,0} 是捕捉了 [i,j] 的牛站在左端点的最少的已花费，f_{i,j,1} 是捕捉了 [i,j] 的牛站在右端点的最少的已花费。

为什么一定是区间捕牛？因为这片区间是走过了，牛不捕白不捕。

转移方程如下：

f_{i,j,0}=\min\{f_{i+1,j,0}+(d_{i+1}-d_{i})\times(c_{1,n}-c_{i+1,j}),f_{i+1,j,1}+(d_{j}-d_{i})\times(c_{i,n}-c_{i+1,j}) f_{i,j,1}=\min\{f_{i,j-1,0}+(d_{j}-d_{i})\times(c_{1,n}-c_{i,j-1}),f_{i,j-1,1}+(d_{j}-d_{j-1})\times(c_{i,n}-c_{i,j-1}) c_{i,j}$ 为 $[i,j]$ 的奶牛个数，也就是 $j-i+1

要排序。不然无序的不能区间 dp。

然而，初始又在哪个端点呢？只要在端点中插入一个位置为 0 的端点，排序后二分即可。

答案是 \min\{f_{1,n,0},f_{1,n,1}\}。

代码实现如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
int f[N][N][2], a[N], d[N], sum[N], n, c;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> d[i];
    d[++ n] = 0, sort(d + 1, d + 1 + n);
    memset(f, 0x3f, sizeof f);
    c = lower_bound(d + 1, d + 1 + n, 0) - d;
    f[c][c][1] = f[c][c][0] = 0;
    for (int k = 2; k <= n; k ++)
        for (int i = 1; i <= n; i ++) {
            int j = i + k - 1;
            f[i][j][0] = min(f[i + 1][j][0] + (d[i + 1] - d[i]) * (i + n - j),
                             f[i + 1][j][1] + (d[j] - d[i]) * (i + n - j));
            f[i][j][1] = min(f[i][j - 1][0] + (d[j] - d[i]) * (i + n - j),
                             f[i][j - 1][1] + (d[j] - d[j - 1]) * (i + n - j));
        }
    cout << min(f[1][n][0], f[1][n][1]) << '\n';
    return 0;
}