[USACO06FEB] Treats for the Cows G/S

题意

给出一排零食，每天只能从最左端或最右端拿走一个卖掉。

第 day 天卖出的第 i 个零食，收益是 v_i * day。要求安排一个最优卖法，使总收益最大。

思路

最直接的想法是递归：今天如果还剩一个区间 [l, r]，就枚举卖左端还是卖右端。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30#include <bits/stdc++.h>
using namespace std;

static int n;
static vector<long long> a;

long long dfs(int l, int r, int day) {
    if (l == r) {
        return a[l] * day;
    }

    // 暴力枚举今天卖左端还是右端。
    long long sell_left = a[l] * day + dfs(l + 1, r, day + 1);
    long long sell_right = a[r] * day + dfs(l, r - 1, day + 1);
    return max(sell_left, sell_right);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    a.assign(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    cout << dfs(1, n, 1) << '\n';
    return 0;
}

brute.cpp 按题意完整枚举每天的选择，复杂度是指数级，只适合做小数据对拍。

关键观察是：当剩余区间为 [l, r] 时，已经卖掉了 n - (r - l + 1) 个零食，所以今天一定是第 n - (r - l + 1) + 1 天。也就是说，只要知道剩余的是哪一段，当前天数也就自动确定了。

因此设 dp[l][r] 表示当前只剩区间 [l, r] 时，后续能获得的最大收益。那么只有两种转移：

先卖左端：dp[l + 1][r] + v_l * day
先卖右端：dp[l][r - 1] + v_r * day

这张表展示几个典型状态的含义：

状态	当前是哪一天	表示什么
`dp[3][3]`	第 `n` 天	只剩一个零食，今天必须卖掉
`dp[2][4]`	第 `n-2` 天	剩下中间连续三段时，后续的最大收益
`dp[1][n]`	第 `1` 天	一开始所有零食都还在，也就是最终答案

读这张表时，重点是把“区间长度”和“当前天数”对应起来。这样状态里就不需要额外再记一天编号，二维区间 DP 就足够了。按区间长度从小到大递推，最终得到 dp[1][n]。

DP 公式

设 $dp_{l,r}$ 表示当前只剩区间 $[l,r]$ 时，后续能获得的最大收益。此时天数由区间长度决定：

day=n-(r-l+1)+1

可以先卖左端或右端：

dp_{l,r}=\max\left(dp_{l+1,r}+v_l\cdot day,\ dp_{l,r-1}+v_r\cdot day\right)

边界为：

dp_{i,i}=v_i\cdot n

最终答案为：

dp_{1,n}

公式解释：剩余区间长度决定当前是第几天，所以状态不必额外记录天数。每一步只能卖左端或右端，卖掉后进入更短的区间，收益加上当前天数乘对应价值。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    vector<vector<long long>> dp(n + 2, vector<long long>(n + 2, 0));

    // dp[l][r] 表示当前只剩区间 [l, r] 这些零食时，后续能获得的最大收益。
    for (int len = 1; len <= n; ++len) {
        int day = n - len + 1;
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            if (l == r) {
                dp[l][r] = a[l] * day;
                continue;
            }
            dp[l][r] = max(
                dp[l + 1][r] + a[l] * day,
                dp[l][r - 1] + a[r] * day
            );
        }
    }

    cout << dp[1][n] << '\n';
    return 0;
}

复杂度

共有 $O(n^2)$ 个区间状态，每个状态只做 $O(1)$ 转移，所以时间复杂度是 $O(n^2)$ ，空间复杂度是 $O(n^2)$ 。

总结

这题的关键不是贪心选左右端，而是识别出“剩余连续区间”就是完整状态。把暴力搜索改写成区间 DP 后，复杂度就从指数级降到了 $O(n^2)$ 。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。