题意
在该题中，请不要使用#include< bits/stdc++.h> 和任何c++11及以上的特性
给出n个数字v(i)，每次你可以取出最左边的数字或者取出最右边的数字，一共取n次取完。假设你第i次取的数字是x，那么你可以获得i*x的价值。现在你需要规划取数顺序，使得总价值和最大。
解题
因为每次取数变化的状态是剩下的数。所以设dp[i][j]表示剩n-i个数且所剩数为第j个数到第j+n-i-1个数。
状态转移方程：
dp[i][j]=dp[i-1][j]+a[j+n-i]*i ， j等于1
dp[i][j]=dp[i-1][j-1]+a[j-1]*i ，j等于i+1
dp[i][j]=max(dp[i-1][j-1]+a[j-1]*i,dp[i-1][j]+a[j+n-i]*i) ，其他情况
时间复杂度为O（n*n）.
空间复杂度为O（n*n）.
AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
typedef long long ll;
using namespace std;const ll maxn=2e3+7;
ll a[maxn],dp[maxn][maxn];int main()
{ll n;scanf("%lld",&n);{for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);memset(dp,0,sizeof(dp));dp[1][1]=a[n];dp[1][2]=a[1];ll ans=max(a[n],a[1]);for(ll i=2;i<n;i++){for(ll j=1;j<=i+1;j++){if(j==n+1) continue;if(j==1) dp[i][j]=dp[i-1][j]+a[j+n-i]*i;else if(j==i+1) dp[i][j]=dp[i-1][j-1]+a[j-1]*i;else dp[i][j]=max(dp[i-1][j-1]+a[j-1]*i,dp[i-1][j]+a[j+n-i]*i);//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;ans=max(ans,dp[i][j]);//cout<<ans<<endl;}}for(ll i=1;i<=n;i++){ans=max(ans,dp[n-1][i]+n*a[i]);}printf("%lld\n",ans);}return 0;
}
/* 9 313 71 711 914 502 230 554 413 585 */