题目链接：http://poj.org/problem?id=3186

思路：

区间DP，给treat编号为1..n，状态很明显是上界i和下界j，dp[i][j]表示从下标i到下标j之间数据的最大价值。可以正向转移，从dp[1][0]开始，也可以逆向转移，从dp[i][i]开始。我这里是正向转移，状态转移方程如下：

    　　 if(i>1&&j<n)

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

            if(i>1&&j==n)

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

            if(i==1&&j<n)

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

其中的（n-1-(j-i))是age。但循环结束后的dp[i][i]并不是最终结果，还需加上n×a[i]。

代码如下：

1 #include
     
       2 #include
      
        3 using namespace std; 4  5 int n,res; 6 int a[2005],dp[2005][2005]; 7  8 int main(){ 9     scanf("%d",&n);10     for(int i=1;i<=n;++i)11         scanf("%d",&a[i]);12     dp[1][n]=0;13     for(int i=1;i<=n;++i)14         for(int j=n;j>=i;--j){15             if(i>1&&j
       
        1&&j==n)18                 dp[i][j]=dp[i-1][j]+(n-1-(j-i))*a[i-1];19             if(i==1&&j