tyvj 1088 treat

描述 Description  
   给出长度为N的数列{A_i}，每次可以从最左边或者最右边取走一个数，第i次取数得到的价值是i * A_j。求价值之和最大的取数方案。

输入格式 Input Format 
   　　第一行，一个整数，表示数列长度N。
　　接下来N行，每行一个整数，表示数列A_i。 
输出格式 Output Format 
   一个整数，表示最大的价值之和。


算法分析:

   设在区间[i,j]按照题目要求取数所获得的最大值为f(i,j),则

    f(i,j) = max{f(i+1,j)+a[i]*(n+i-j),f(i,j-1)+a[i]*(n+i-j)}

    f(i,i) = a[i]*n

代码:

#include <iostream>
#include <memory.h>
using namespace std;
const int maxn = 2010;
int a[maxn];
int f[maxn][maxn];
int n;
int dp(int i,int j)
{
    if(f[i][j]!=-1)   return f[i][j];
    return f[i][j]=max(dp(i+1,j)+a[i]*(n+i-j),dp(i,j-1)+a[j]*(n+i-j));
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>a[i];
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;i++)   f[i][i]=n*a[i];
    cout<<dp(1,n)<<endl;
    
    return 0;
}