/**     http://bestmind.space/posts/%E9%93%BE%E5%AE%B62018%E9%93%BE%E4%B9%A0%E7%94%9F%E6%8B%9B%E8%81%98%E8%80%83%E8%AF%95-%E7%BC%96%E7%A8%8B%E9%A2%98%E4%B8%89/     链家笔试第一题，食品那题     分析：使用动态规划         1.定义dp(i,j)，表示除了编号从i到j的食物，剩下卖出的最大值。         2.状态转移方程为：             dp(i,j) = Max{dp(i-1,j)+cost(i-1), dp(i,j+1)+cost(j+1)}             dp(i-1,j)+cost(i-1)：除了(i-1,j)卖出的最大值加上卖出第(i-1)的价值。             dp(i,j+1)+cost(j+1)：除了(i,j+1)卖出的最大值加上卖出第(j+1)的价值。         3.空间复杂度O(n*n)可以优化为O(n)。 */ int n, v[2002], dp[2002], maxIncome; int main() {     memset(dp, 0, sizeof dp);     maxIncome = 0;     cin >> n;     // 数组下标从1开始     v[0] = v[n+1] = 0;     for(int i = 1; i <= n; i++)         cin >> v[i];     // 从右往左dp     for(int i = 1; i <= n; i++) {         int day = i - 1;         // 求出dp[i, n~i]         for(int j = n; j >= i; j--) {             dp[j] = max(dp[j] + v[i-1]*day, dp[j+1] + v[j+1]*day);             day++;         }         // 上面计算得到的dp[i],表示的是除了第i个食物所得到的最大值,         // 因此还需选上第i个食物, 即最后一个选的是i         maxIncome = max(maxIncome, dp[i] + v[i]*n);     }     cout << maxIncome;     return 0; }