spoj治療奶牛DP得到錯誤的答案？

Question

爲什麼我得到錯誤的答案。我已經使用DP並將表格填滿。

http://www.spoj.com/problems/TRT/

for(int i=0;i<n;i++) 
    { 
     dp[i][i]=n*a[i]; 
    } 

    for(int i=n-2;i>=0;i--) 
    { 
     for(int j=i+1;j<n;j++) 
     { 
      dp[i][j]=max((i+1)*a[i]+dp[i+1][j],dp[i][j-1]+(i+1)*a[j]);//(i+1) is the age 

     } 
    } 
    printf("%d\n",dp[0][n-1]); 

Answer 1

年齡不會是我+ 1。它將是n + i-j。

dp[i][j] = max( (n+i-j)*a[i]+dp[i+1][j], dp[i][j-1] + (n+i-j)*a[j]);