记录编号	566421	评测结果	AAAAAAAAAA
题目名称	[USACO Feb06]特殊津贴	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	0.240 s
提交时间	2021-11-07 21:02:33	内存使用	21.08 MiB

#include<bits/stdc++.h>
#define ull unsigned long long 
#define ll long long 
using namespace std;
int nc;
int n[2005]; 
int f[2005][2005];
int DP(int cl,int l,int r)
{
	if(l>r) return 0;;  
	if(f[l][r]) return f[l][r];
	f[l][r]=max(DP(cl+1,l+1,r)+cl*n[l],DP(cl+1,l,r-1)+cl*n[r]);
	return f[l][r];
}
int main()
{
	freopen("treats.in","r",stdin);
	freopen("treats.out","w",stdout);
    scanf("%d",&nc);
    for(int i=1;i<=nc;i++)
    {
    	scanf("%d",&n[i]);
    }
	DP(1,1,nc);
    printf("%d\n",f[1][nc]);
	return 0;
}