[USACO06FEB] 奶牛零食(Treats for the Cows) 题解

思路分析

注意「每天贪心卖两端较小者」是错误的（例如两端相等但其内侧元素差异巨大时）。正确做法是区间 DP：当盒中还剩闭区间 $[l, r]$（长度为 $len = r - l + 1$）未售出时，当前恰好是第 $a = N - len + 1$ 天。按区间长度 $len$ 从 $1$ 到 $N$ 递推：dp[l][r] = max(dp[l + 1][r] + v[l] * a, dp[l][r - 1] + v[r] * a)，最终答案为 dp[1][N]。时间复杂度 $O(N^2)$。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

int v[2005];
long long dp[2005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) cin >> v[i];

    for (int i = 1; i <= n; ++i) dp[i] = 1LL * v[i] * n;
    for (int len = 2; len <= n; ++len)
    {
        long long age = n - len + 1;
        for (int l = 1; l + len - 1 <= n; ++l)
        {
            int r = l + len - 1;
            dp[l] = max(dp[l + 1] + age * v[l], dp[l] + age * v[r]);
        }
    }
    cout << dp[1] << "\n";
    return 0;
}