首页 > 其他分享 >[USACO06FEB]Treats for the Cows G/S

[USACO06FEB]Treats for the Cows G/S

时间:2023-06-13 20:44:06浏览次数:50  
标签:约翰 treats int USACO06FEB treat Cows FJ 零食 Treats

[USACO06FEB]Treats for the Cows G/S

题目描述

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 \leq N \leq 2000\)) 份美味的零食来卖给奶牛们。每天约翰售出一份零食。当然约翰希望这些零食全部售出后能得到最大的收益,这些零食有以下这些有趣的特性:

  • 零食按照 \(1, \ldots, N\) 编号,它们被排成一列放在一个很长的盒子里。盒子的两端都有开口,约翰每天可以从盒子的任一端取出最外面的一个。
  • 与美酒与好吃的奶酪相似,这些零食储存得越久就越好吃。当然,这样约翰就可以把它们卖出更高的价钱。
  • 每份零食的初始价值不一定相同。约翰进货时,第i份零食的初始价值为 \(V_i\)(\(1 \leq V \leq 1000\))。
  • 第i份零食如果在被买进后的第 \(a\) 天出售,则它的售价是 \(V_i \times a\)。

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

输入格式

Line 1: A single integer, N

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

输出格式

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

样例 #1

样例输入 #1

5
1
3
1
5
2

样例输出 #1

43

提示

Explanation of the sample:

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

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.

解析

方法核心:DP

此题最重要的就是找到dp的状态转移方程。对于某些神犇来说这并不是什么难事,可是只要经过一定量的练习后,这道题可能就显得没有这么难了(对于某些神犇来说,这题本身就不难)

首先回顾合并果子。那题的状态定义为:\(f_{i,j}\) 表示将这堆果子堆在i~j的闭区间内的最大得分。

此题可以效仿。同样f[i][j]表示只剩下\(i-j\)的闭区间内的零食是赚到的最多的钱。

接下来是状态转移方程。不难发现,\(f_{i,j}\) 的上一个状态是 \(f_{i-1,j}\) 或\(f_{i,j+1}\) ,这样状态转移方程就写好了:

\[f[i][j]=max(f[i-1][j]+v[i-1]*a,f[i][j+1]+v[j+1]*a); \]

其中,\(a\) 表示零食在被买进后的第a天出售,表达式 a=n-(j-i+1)

分析到这里,这道题基本大功告成了。

代码:

#include<bits/stdc++.h>
using namespace std;
int n,f[2010][2010],v[2010];
int main()
{
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> v[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=n;j>=i;j--)
		{
			int a=n-(j-i+1);
			f[i][j]=max(f[i-1][j]+v[i-1]*a,f[i][j+1]+v[j+1]*a);//转移
		}
	}
	int maxn=0;
	for(int i=1;i<=n;i++)
	{
		maxn=max(maxn,f[i][i]+v[i]*n);//记得把最后的卖出去
	} 
	cout << maxn;
}

总结:

这题是一道区间 dp 的好题,建议当做模板题练练,熟悉以处理区间端点作为下标的 dp 类型,再回过头看这一题就显而易见了

标签:约翰,treats,int,USACO06FEB,treat,Cows,FJ,零食,Treats
From: https://www.cnblogs.com/momotrace/p/p2858.html

相关文章

  • Codeforces Round #225 (Div. 2)-C. Milking cows
    原题链接C.Milkingcowstimelimitpertestmemorylimitpertestinputoutputn cowssittinginarow,numberedfrom 1 to nIahubcandecidetheorderinwhichhemilksthecows.Buthemustmilkeachcowex......
  • (输出路径搜索)[USACO06OCT] Cows on Skates G
    题目描述本题使用SpecialJudge。FarmerJohn把农场划分为了一个 r 行 c 列的矩阵,并发现奶牛们无法通过其中一些区域。此刻,Bessie位于坐标为 (1,1)(1,1) 的区域,并想到坐标为 (,)(r,c) 的牛棚享用晚餐。她知道,以她所在的区域为起点,每次移动至相邻的四个区域之一,总有......
  • P1676 [USACO05FEB] Aggressive cows G 题解
    题目传送门解题思路最大值最小化问题,考虑二分答案。首先要排序,保证序列单调不降,然后求出两个隔间之间的距离。sort(a+1,a+1+n);for(rii=1;i<=n;i++) dis[i]=a[i+1]-a[i];二分出一个\(mid\),判断它是否合法:每次累加距离,如果距离和比\(mid\)大,说明当前可以分配牛,记录数量......
  • NC51101 Lost Cows
    题目链接题目题目描述\(N(2\leqN\leq8,000)\)cowshaveuniquebrandsintherange1..N.Inaspectaculardisplayofpoorjudgment,theyvisitedtheneighborhood'wateringhole'anddrankafewtoomanybeersbeforedinner.Whenitwastimetoli......
  • Codeforces Round #225 (Div. 2) C. Milking cows Greedy
    Iahubhelpshisgrandfatheratthefarm.Todayhemustmilkthecows.Therearencowssittinginarow,numberedfrom1tonfromlefttoright.Eachcowiseitherfacingtotheleftorfacingtotheright.WhenIahubmilksacow,allthecowsthatseet......
  • POJ - 3186 Treats for the Cows(DP)
    题目大意:给你一个数组,每次你可以取两个数中的一个进行操作,要么取数组的第一个,要么数组的最后一个(取完之后,该数删除)假设取出来的数组组成了A现在要求使Sum=A[1]*1+A[2]*2+A[3]*3…+A[n]*n达到最大解题思路:用dp[i][j]表示前面取了i个,后面取了j个最大值则转......
  • J - Til the Cows Come Home
    J-TiltheCowsComeHomeBessieisoutinthefieldandwantstogetbacktothebarntogetasmuchsleepaspossiblebeforeFarmerJohnwakesherforthem......
  • Popular Cows
    PopularCowshttp://poj.org/problem?id=2186 思路涉及到有向图的强连通子图检测,参考:https://oi-wiki.org/graph/scc/https://www.cnblogs.com/zwfymqz/p/6693881.h......
  • Til the Cows Come Home ( POJ 2387) (简单最短路 Dijkstra)
    problemBessieisoutinthefieldandwantstogetbacktothebarntogetasmuchsleepaspossiblebeforeFarmerJohnwakesherforthemorningmilking.......
  • POJ--2456 Aggressive cows(二分搜索/最大化最小值)
    记录22:552023-2-9http://poj.org/problem?id=2456reference:《挑战程序设计竞赛(第2版)》3.1.3p142DescriptionFarmerJohnhasbuiltanewlongbarn,withN(2......