dp[i][j]表示区间 i~区间 j 的最大value,区间长度为j - i + 1,转移方程即为： dp[i][j] = max(dp[i + 1][j] + v[i] * (n - i - j),dp[i][j - 1] + v[j] * (n - i - j)) 先更新短区间，则更新长区间时短区间已经被更新完毕，故dp[1][n]即为最终答案。
#include<iostream> #include<vector> #define debug(x) cout<<#x<<" is "<<x<<endl #define pb push_back using namespace std; typedef long long ll; ll ans; const int N = 2e3 + 5; int a[N]; ll dp[N][N]; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for(int i = 1;i <= n;i++){ cin>>a[i]; dp[i][i] = n * a[i]; } for(int i = 1;i <= n - 1;i++){// i：length for(int j = 1; j + i <= n;j++){//j : 开始下标 dp[j][j + i] = max(dp[j][j + i - 1] + (n - i) * a[j + i],dp[j + 1][j + i] + (n - i) * a[j]); } } cout<<dp[1][n]<<endl; return 0; }