题目大意：
约翰经常给产奶量高的奶牛发特殊津贴，于是很快奶牛们拥有了大笔不知该怎么花的钱．为此，约翰购置了 (N(1 le N le 2000)) 份美味的零食来卖给奶牛们．每天约翰售出一份零食．当然约翰希望这些零食全部售出后能得到最大的收益．这些零食有以下这些有趣的特性：
- 零食按照 (1 cdots N) 编号，它们被排成一列放在一个很长的盒子里．盒子的两端都有开口，约翰每天可以从盒子的任一端取出最外面的一个.
- 与美酒与好吃的奶酪相似，这些零食储存得越久就越好吃．当然，这样约翰就可以把它们卖出更高的价钱.
- 每份零食的初始价值不一定相同．约翰进货时，第 (i) 份零食的初始价值为 (V_i(1 le V_i le 1000)) .
- 第 (i) 份零食如果在被买进后的第 (a) 天出售，则它的售价是 (V_i imes a) .
(V_i) 是从盒子顶端往下的第i份零食的初始价值．约翰告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱．
解题思路：
我们定义状态 (f[L][R]) 为将区间 ([L,R]) 依次去空能能够获得最多的钱。
那么我们可以发现我们的答案就是 (f[1][n]) ，那么怎么求解 (f[1][n]) 呢？先不急，听我细细道来~
假设我们现在要求解 (f[L][R]) ，那么我们可以发现，对于区间 ([L,R]) ，我们取走一份零食的方案只有两种：
- 方案一：从左边取走 (V_L) ，然后状态变成了 (f[L+1][R])；
- 方案二：从右边取走 (V_R) ，然后状态变成了 (f[L][R-1])。
对于区间 ([L,R]) ，首先我们要确定我们取走的零食（无论是方案一还是方案二）是第几份取走的零食？
我们可以发现，([L,R]) 区间的左边有 (L-1) 份零食在之前被取走了，右边有 (n-R) 份零食在之前被取走了，所以我们现在取的零食是第 (L-1 + n-R + 1 = n+L-R) 份。
所以采用第一种方案能够获得的最多的钱是
采用第二种方案能够获得的最多的钱是
那我们现在要求解的状态 (f[L][R]) 应该是两种方案的较大值，所以我们可以得到最终的状态转移方程如下：
当然，还需要注意的情况是我们的边界条件，即：区间长度为 (1) 时的情况，此时，对于所有的区间 ([i,i]) ，第 (i) 份零食都是最后取走的（即第 (n) 份被取走的），所以
基于上面的推导，我们可以通过记忆化搜索的形式实现我们的主要代码：
int dfs(int L, int R) {
if (f[L][R]) // 记忆化操作
return f[L][R];
if (L == R) // 边界条件
return V[L] * n;
return f[L][R] = max(dfs(L+1, R)+V[L]*(n+L-R), dfs(L, R-1)+V[R]*(n+L-R));
}
记忆化搜索的思想还是非常对应我们人脑的思考方式的，我们可以发现，这个程序主要分为三部分：
首先我们的 dfs(L,R) 就是为了返回 (f[L][R])，所以它：
- 首先判断是不是已经计算过了（通过 (f[L][R]) 是否为 (0) 来判断），如果已经计算过了直接发挥结果；
- 其次判断是不是边界条件（通过 (L) 是否等于 (R) 来判断），如果是边界条件直接返回 (V_L imes n)；
- 最后计算并记录值，以便下一次计算的时候直接返回。
使用记忆化搜索的完整代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2020;
int n, V[maxn], f[maxn][maxn];
int dfs(int L, int R) {
if (f[L][R]) // 记忆化操作
return f[L][R];
if (L == R) // 边界条件
return V[L] * n;
return f[L][R] = max(dfs(L+1, R)+V[L]*(n+L-R), dfs(L, R-1)+V[R]*(n+L-R));
}
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> V[i];
cout << dfs(1, n) << endl;
return 0;
}
我们也可以采用一般形式来解决这个问题（一般形式和记忆化搜索形式的思路都是一样的，只不过一个是直接for循环顺着来，另一个是递归着来，要注意区分和类比）。
我们可以发现，大区间（即区间长度较大的区间）对应的状态都是通过小区间（即区间长度较小的区间）对应的状态推导出来的，所以我们只要从小到大遍历区间长度，再遍历区间左坐标，计算对应状态即可。
主要代码如下：
for (int l = 1; l <= n; l ++) { // 从小到大遍历区间长度l
for (int i = 1; i+l-1 <= n; i ++) { // 遍历区间左边界i
int j = i+l-1; // 通过左边界i和区间长度l获得区间右边界j
if (l == 1) f[i][j] = V[i]*n; // 边界条件直接返回结果
else f[i][j] = max(f[i+1][j] + V[i]*(n+i-j), f[i][j-1] + V[j]*(n+i-j)); // 否则，通过状态转移方程推导
}
}
一般形式的完整实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2020;
int n, V[maxn], f[maxn][maxn];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> V[i];
for (int l = 1; l <= n; l ++) { // 从小到大遍历区间长度l
for (int i = 1; i+l-1 <= n; i ++) { // 遍历区间左边界i
int j = i+l-1; // 通过左边界i和区间长度l获得区间右边界j
if (l == 1) f[i][j] = V[i]*n; // 边界条件直接返回结果
else f[i][j] = max(f[i+1][j] + V[i]*(n+i-j), f[i][j-1] + V[j]*(n+i-j)); // 否则，通过状态转移方程推导
}
}
cout << f[1][n] << endl;
return 0;
}