BZOJ 1652: [Usaco2006 Feb]Treats for the Cows (区间dp)

1652: [Usaco2006 Feb]Treats for the Cows

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 290  Solved: 226
[Submit][Status][Discuss]

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.

约翰经常给产奶量高的奶牛发特殊津贴,于是很快奶牛们拥有了大笔不知该怎么花的钱.为此,约翰购置了N(1≤N≤2000)份美味的零食来卖给奶牛们.每天约翰售出一份零食.当然约翰希望这些零食全部售出后能得到最大的收益.这些零食有以下这些有趣的特性:

•零食按照1..N编号,它们被排成一列放在一个很长的盒子里.盒子的两端都有开口,约翰每
  天可以从盒子的任一端取出最外面的一个.
•与美酒与好吃的奶酪相似,这些零食储存得越久就越好吃.当然,这样约翰就可以把它们卖出更高的价钱.
  •每份零食的初始价值不一定相同.约翰进货时,第i份零食的初始价值为Vi(1≤Vi≤1000).
  •第i份零食如果在被买进后的第a天出售,则它的售价是vi×a.
  Vi的是从盒子顶端往下的第i份零食的初始价值.约翰告诉了你所有零食的初始价值,并希望你能帮他计算一下,在这些零食全被卖出后,他最多能得到多少钱.

Input

* Line 1: A single integer,

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

Output

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

Sample Input

5
1
3
1
5
2

Five treats. On the first day FJ can sell either treat #1 (value 1) or
treat #5 (value 2).

Sample Output

43

OUTPUT DETAILS:

FJ sells the treats (values 1, 3, 1, 5, 2) in the following order
of indices: 1, 5, 2, 3, 4, making 1×1 + 2×2 + 3×3 + 4×1 + 5×5 = 43.

题意:一列数,可以从两段取,每天取一个数,第t天取到第i个数的价值是t*v[i],问能取到的最大价值是多少。
思路:能看出是dp.不过状态表示这一步就错了。。。我想的是dp[i]表示第i天取能得到的最大价值。。。然后转移方程就推不对了23333.
实际上这种从两段搞的问题的状态,还是要两个变量来表示状态比较好。
dp[i][j]表示最左端为i,最右端为j能得到的最大价值。
而且这道题的划分状态也很厉害。反正我是没想到。
定义了k表示为当前剩余区间的长度。
容易知道k=j-i+1;
那么t=n+i-j,j = n-k+1;
像很多dp一样,这道题也需要倒着推。。。
也就是从长度为1的区间推到长度为n的区间。
转移方程为dp[i][j] = max(dp[i+1][j]+t*v[i],dp[i][j-1]*v[j])
(注意观察,(i,j)的状态是由(i+1,j)或者(i,j-1)得到的,因为是从里向外推。)

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz