Treats for the Cows G/S

思路

状态表示：f[l][r]代表从1到n的区间卖到l到r这个区间，l到r这个区间能卖出的钱.

一个区间要么先卖左边要么先卖右边.

先卖左边,就是f[l+1][r]+ a[l]卖的钱,a[l]卖的钱是它的价值×天数，天数就是(n-长度+1)。右边同理

状态转移方程:$f[l][r]=max(f[l][r-1]+a[r]*(n-长度+1),f[l+1][r]+a[l]*(n-长度+1))$

初始化:f[i][i]=a[i]*n

代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[2010],f[2010][2010];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
     {
        cin>>a[i];
        f[i][i]=a[i]*n;
    } 
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i<=n-len+1;i++)
        {
            int j=i+len-1;
            f[i][j]=max(f[i][j-1]+a[j]*(n-len+1),f[i+1][j]+a[i]*(n-len+1));
        }    
    }
    cout<<f[1][n];
}