题目描述 Farmer John有n（1≤n≤2000）个美味的食物，他想卖掉它们来赚钱给奶牛。这些食物放在一些箱子里，它们有些有趣的特性： （1）这些食物被编号为1-n，每一天Farmer John可以从这排箱子的头部或者尾部取出食物去卖； （2）这些食物放得越久，年龄越大，价值越大，食物i有一个初始的价值v（i）； （3）放了a天后，年龄为a，食物最终的价值为v（i）×a。 给定每一个食物的初始价值v（i），请求出FJ卖掉它们后可以获得的最大价值，第一天出售的食物年龄为1，此后每增加一天食物的年龄就增加1。 输入格式 第一行，一个整数n； 第2×n+1行，每行为食物i的初始价值v（i）。 输出格式 一行，为FJ最终可以获得的最大价值。给出完整的c++代码

以下是C++代码实现：

#include<iostream>
#include<cstring>

using namespace std;

const int N = 2010;

int n;
int v[N];
int dp[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> v[i];

    memset(dp, 0xc0, sizeof dp);  // 将dp数组初始化为负无穷

    for(int i = 1; i <= n; i++) dp[i][i] = n * v[i]; // 初始化dp数组

    for(int len = 2; len <= n; len++)  // 枚举区间长度
        for(int l = 1; l + len - 1 <= n; l++)  // 枚举区间左端点
        {
            int r = l + len - 1;  // 区间右端点
            dp[l][r] = max(dp[l + 1][r] + v[l] * (n - len + 1), dp[l][r - 1] + v[r] * (n - len + 1));
        }

    cout << dp[1][n] << endl;

    return 0;
}

算法思路：

这是一道区间DP的题目，我们可以用dp[l][r]表示区间[l, r]内能够获得的最大价值。因为每天卖出的食物年龄都会增加1，因此我们可以用n - len + 1表示第一天卖出的食物年龄。

状态转移方程为：dp[l][r] = max(dp[l + 1][r] + v[l] * (n - len + 1), dp[l][r - 1] + v[r] * (n - len + 1))，表示在区间[l, r - 1]中卖掉一件食物或在区间[l + 1, r]中卖掉一件食物，取最大值即可。

时间复杂度为O(n ^ 2)。