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 1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 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)得到的，因为是从里向外推。）
1/* ***********************************************
2Author :111qqz
3Created Time :2016年04月11日 星期一 20时46分42秒
4File Name :code/bzoj/1652.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=2E3+3;
34int dp[N][N];//dp[i][j]表示最左边取i,最右边取j的最大值。
35int n;
36int v[N];
37bool vis[N];
38int main()
39{
40 #ifndef ONLINE_JUDGE
41 freopen("code/in.txt","r",stdin);
42 #endif
43
44 scanf("%d",&n);
45 v[0] = 0 ;
46 for ( int i = 1 ; i <= n ; i++) scanf("%d",&v[i]);
47 ms(dp,0);
48
49 for ( int k = 1 ; k <= n ; k++) //k是i两段的间隔距离，也可以理解成剩余的长度。k=j-i+1;
50 { //这个划分状态的技巧有点厉害
51 for ( int i = 1 ; i+k-1 <= n ; i++)
52 {
53 int t = n-k+1;
54 int j = i+k-1;
55// cout<<"i:"<<i<<" j:"<<j<<" t:"<<t<<endl;
56 dp[i][j] = max(dp[i+1][j]+t*v[i],dp[i][j-1]+t*v[j]); //转移是倒着进行的，从内向外
57 }
58 }
59
60 printf("%d\n",dp[1][n]);
61
62 #ifndef ONLINE_JUDGE
63 fclose(stdin);
64 #endif
65 return 0;
66}