- 设dp[i][j]表示跳完这一段的最大值,考虑状态转移，由于每次只能向右跳或者向左跳，且跳跃次数即为区间的长度
- dp[i][j] = max(dp[i-1][j]+(j-i+1) * arr[i],dp[i][j-1]+(j-i+1) * arr[j]);
https://ac.nowcoder.com/acm/contest/24213/1061
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n;
int arr[4050];
int dp[4050][4050];
int main(){
cin>>n;
for(int i = 1;i<=n;i++) cin>>arr[i],arr[i+n] = arr[i];
for(int i = 1;i<=n*2;i++) dp[i][i] = arr[i];
//跳跃次数即为右区间减左区间加一
for(int len = 2;len<=n;len++){
for(int i = 1;i<=2*n&&i+len-1<=2*n;i++){
int j = i+len-1;
dp[i][j] = max(dp[i+1][j]+(j-i+1)*arr[i],dp[i][j-1]+(j-i+1)*arr[j]);
}
}
int ans = -1;
// cout<<dp[3][5]<<endl;
for(int i = 1;i<=n;i++){
ans = max(ans,dp[i][i+n-1]);
}
cout<<ans;
}