# [BZOJ1652]&&[Usaco2006 Feb]Treats for the Cows

## 描述 Description

FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time. The treats are interesting for many reasons: * The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats. * Like fine wines and delicious cheeses, the treats improve with age and command greater prices. * The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000). * Cows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a. Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally? The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.

• 与美酒与好吃的奶酪相似，这些零食储存得越久就越好吃．当然，这样约翰就可以把它们卖出更高的价钱．

• 每份零食的初始价值不一定相同．约翰进货时，第 i 份零食的初始价值为 Vi(1≤Vi≤1000)．

• 第 i 份零食如果在被买进后的第 a 天出售，则它的售价是 vi×a．

Vi 的是从盒子顶端往下的第 i 份零食的初始价值．约翰告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱．

## 输入格式 InputFormat

Line 1: A single integer,N.

Lines 2..N+1: Line i+1 contains the value of treat v(i).

## 输出格式 OutputFormat

Line 1: The maximum revenue FJ can achieve by selling the treats

10
284
983
417
263
700
237
481
67
13
767

26544

Silver

BZOJ 1652

## 代码 Code

f[i][j]=Max \lbrace \begin{aligned} &f[i][j-1]+a[j]*k \\\\ &f[i+1][j]+a[i]*k \end{aligned} \rbrace

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
using namespace std;
int a;
int f;
int i,j,t,n,m,l,r,k,z,y,x;
inline int read()
{
int x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
int main()
{
n=read();
for (i=1;i<=n;i++) a[i]=read(),f[i][i]=a[i]*n;
for (k=2;k<=n;k++) for (i=1;i<=n-k+1;i++)
{
j=i+k-1;t=n-k+1;
f[i][j]=max(f[i][j-1]+a[j]*t,f[i+1][j]+a[i]*t);
}
printf("%dn",f[n]);
return 0;
}