一开始想到的是，用一个标志位记录取第i个数的时间，但后来发现这个方法不行，可能性太多，没办法推

然后就看了解题报告的思路，说是用区间dp，状态是设出来了，但受固有思维影响，老想着怎么顺着推。

最后实在想不出了，看了代码，才发现要逆着推，从结束状态开始推起，这样公式就出来了

为了保证每一层循环要用到的值都已经被计算出来了，按区间长度进行枚举

纪念第一个区间dp吧

?

/*
dp[i][j]:剩下第i个至第j个物品时，取掉剩下的所有物品能获得的最大值 
dp[i][j]=max(dp[i+1][j]+v[i]*(n-(j-i+1)+1),dp[i][j-1]+v[j]*(n-(j-i+1)+1));
*/
#include
  
   
#include
   
     #include
    
      using namespace std; int n,v[2005],dp[2005][2005]; void init(){ //memset(dp,-1,sizeof(dp)); for(int i=1;i<=n;i++) dp[i][i]=v[i]*n; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&v[i]); int tmp; init(); int j; for(int l=2;l<=n;l++){//逆着推，从最后出队列的开始推起，按区间长度枚举 for(int i=1;i<=n;i++){ j=i+l-1; dp[i][j]=max(dp[i+1][j]+v[i]*(n-(l-1)),dp[i][j-1]+v[j]*(n-(l-1))); } } printf("%d\n",dp[1][n]); }
    
   
  

?