文字教学

这是一道区间动态规划问题，核心是用 dp[i][j] 表示剩下第 i 到 j 份零食时能获得的最大收益。

1. 状态定义：dp[i][j] 表示剩余零食为第 i 到 j 份时的最大收益。
2. 初始状态：当只剩一份零食（i==j）时，它是第 N 天卖出，所以 dp[i][i] = V[i] * N。
3. 状态转移：对于区间 i 到 j，已卖了 N - (j-i+1) 天，今天是第 N - (j-i+1) + 1 = N - j + i 天。有两种选择：
   • 取左边的 i：收益为 V[i] * 天数 + dp[i+1][j]
   • 取右边的 j：收益为 V[j] * 天数 + dp[i][j-1] 取两者最大值作为 dp[i][j]。
4. 最终答案：dp[1][N] 就是全部卖完的最大收益。

代码

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }
    for (int i = 1; i <= n; ++i) {
        dp[i][i] = v[i] * n;
    }
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            int day = n - len + 1;
            dp[i][j] = max(v[i] * day + dp[i+1][j], v[j] * day + dp[i][j-1]);
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}