↓ 跳过正文
111qqz的小窝
111qqz的小窝
  1. Posts/

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

·1352 字·3 分钟
ACM 区间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 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}

相关文章

hdu 1160 FatMouse's Speed (最长上升子序列)

·769 字·2 分钟
ACM DP 区间DP
FatMouse’s Speed # Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10172 Accepted Submission(s): 4521 Special Judge Problem Description FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.

hdu 1114 - Piggy-Bank (完全背包)

·774 字·2 分钟
ACM DP 区间DP 完全背包
F - Piggy-Bank **Time Limit:**1000MS **Memory Limit:**32768KB 64bit IO Format:%I64d & %I64u Submit Status Description Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid.

hdu 1087 - Super Jumping! Jumping! Jumping! (最长上升子序列)

·536 字·2 分钟
ACM DP 区间DP
E - Super Jumping! Jumping! Jumping! **Time Limit:**1000MS **Memory Limit:**32768KB 64bit IO Format:%I64d & %I64u Submit Status Description Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now. The game can be played by two or more than two players. It consists of a chessboard（棋盘）and some chessmen（棋子）, and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of jumping, the player will visit the chessmen in the path, but everyone must jumps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across many chessmen, and even you can straightly get to end-point from start-point. Of course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumping path. Your task is to output the maximum value according to the given chessmen list.

BZOJ 1651: [Usaco2006 Feb]Stall Reservations 专用牛棚 (前缀和)

·626 字·2 分钟
ACM 前缀和
1651: [Usaco2006 Feb]Stall Reservations 专用牛棚 # Time Limit: 10 Sec Memory Limit: 64 MB Submit: 700 Solved: 393 [Submit][Status][Discuss] Description # Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows. Help FJ by determining: * The minimum number of stalls required in the barn so that each cow can have her private milking period * An assignment of cows to these stalls over time

BZOJ 1650: [Usaco2006 Dec]River Hopscotch 跳石子 (二分)

·1042 字·3 分钟
ACM 二分
1650: [Usaco2006 Dec]River Hopscotch 跳石子 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 440 Solved: 290 [Submit][Status][Discuss] Description # Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 <= L <= 1,000,000,000). Along the river between the starting and ending rocks, N (0 <= N <= 50,000) more rocks appear, each at an integral distance Di from the start (0 < Di < L). To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river. Farmer John is proud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to M rocks (0 <= M <= N). FJ wants to know exactly how much he can increase the shortest distance before he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.