洛谷p2858[usaco06feb]奶牛零食treatsforthecows

关键词：

题目描述

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份零食的初始价值．约翰告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱．

输入输出格式

输入格式：

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

输入输出样例

5
1
3
1
5
2

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

普通搜索 54分

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,ans,v[2020];

void dfs(int ste,int l,int r,int sum){
    if(l==r){
        ans=max(ans,sum+v[l]*ste);
        return;
    }
    dfs(ste+1,l+1,r,sum+ste*v[l]);
    dfs(ste+1,l,r-1,sum+ste*v[r]);
}

int main(){
    scanf("%d",&n);ans=0;
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    dfs(1,1,n,0);
    cout<<ans<<endl;
    return 0;
}

记忆化搜索 AC

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,ans,v[2020],f[2020][2020];

int dfs(int ste,int l,int r){
    if(r<l)return 0;
    if(f[l][r])return f[l][r];
    f[l][r]=max(dfs(ste+1,l+1,r)+ste*v[l],dfs(ste+1,l,r-1)+ste*v[r]);
    return f[l][r];
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    dfs(1,1,n);
    printf("%d",f[1][n]);
    return 0;
}

区间dp AC 第一层循环枚举区间长度，第二层循环枚举左端点。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,f[2017][2017],v[2017];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)f[i][i]=v[i]*n;//一开始初始化忘记乘以n 
    for(int i=2;i<=n;i++){
        for(int l=1;l<=n;l++){
            int r=l+i-1;
            if(r>n)break;
            f[l][r]=max(f[l][r-1]+v[r]*(n-i+1),f[l+1][r]+v[l]*(n-i+1));
        }
    }
    printf("%d
",f[1][n]);
    return 0;
}

p2858[usaco06feb]奶牛零食treatsforthecows

题目描述FJhaspurchasedN(1<=N<=2000)yummytreatsforthecowswhogetmoneyforgivingvastamountsofmilk.FJsellsonetreatperdayandwantstomaximizethemoneyhereceivesoveragivenperiodtime.Thetreatsareinterestingfor 查看详情

p2858[usaco06feb]奶牛零食treatsforthecows

P2858[USACO06FEB]奶牛零食TreatsfortheCows区间dp，级像矩阵取数，f[i][i+l]=max(f[i+1][i+l]+a[i]*(m-l),f[i][i+l-1]+a[i+l]*(m-l));1#include<iostream>2#include<cstdio>3#include<queue>4#include<algor 查看详情

洛谷p2858·动态规划[usaco06feb]奶牛零食treatsforthecows

题面题目描述FJhaspurchasedN(1<=N<=2000)yummytreatsforthecowswhogetmoneyforgivingvastamountsofmilk.FJsellsonetreatperdayandwantstomaximizethemoneyhereceivesoveragivenperiodtime.Thetreatsareinterestingf 查看详情

[luogup2858][usaco06feb]奶牛零食treatsforthecows（dp）

传送门 f[i][j][k]表示左右两段取到i....j时，取k次的最优解可以优化k其实等于n-j+i则f[i][j]=max(f[i+1][j]+a[i]*(n-j+i),f[i][j-1]+a[j]*(n-j+i))边界f[i][i]=a[i]*n递推顺序不好求，所以选择记忆化搜索。 ——代码1#include<cstdio>2#incl 查看详情

bzoj1652[usaco2006feb]treatsforthecows区间动归

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

p2857[usaco06feb]稳定奶牛分配steadycowassignment(代码片段)

题目描述FarmerJohn‘sN(1<=N<=1000)cowseachresideinoneofB(1<=B<=20)barnswhich,ofcourse,havelimitedcapacity.Somecowsreallyliketheircurrentbarn,andsomearenotsohappy.FJwouldliketorearrangethecowssu 查看详情

洛谷p3659[usaco17feb]whydidthecowcrosstheroadig

//神题目（题目一开始就理解错了）。。。题目描述Whydidthecowcrosstheroad?Well,onereasonisthatFarmerJohn‘sfarmsimplyhasalotofroads,makingitimpossibleforhiscowstotravelaroundwithoutcrossingmanyofthem.奶牛们为什么要穿马路？一个原因只是因为FJ的牧场的路 查看详情

洛谷p1118[usaco06feb]数字三角形backwarddigitsums

题目描述FJandhiscowsenjoyplayingamentalgame.Theywritedownthenumbersfrom1toN(1<=N<=10)inacertainorderandthensumadjacentnumberstoproduceanewlistwithonefewernumber.Theyrepeatthisuntilonlyasinglenumberi 查看详情

洛谷p1118[usaco06feb]数字三角形搜索

洛谷P1118[USACO06FEB]数字三角形BackwardDigitSu…  搜索这题我们发现每一个位置的加权就是杨辉三角yh[n][i]然后我们就可以求n!暴力，但是会TLE额好像是会T因为12!已经4亿了然后我们加一个强力剪枝如果当前求出来的s已经大于sum... 查看详情

p2859[usaco06feb]stallreservationss（区间问题，堆）(代码片段)

题目描述约翰的N(l<N<50000)头奶牛实在是太难伺候了，她们甚至有自己独特的产奶时段.当然对于某一头奶牛，她每天的产奶时段是固定的，为时间段A到B包括时间段A和时间段B.显然，约翰必须开发一个调控系统... 查看详情

p2859[usaco06feb]stallreservationss（区间问题，堆）(代码片段)

题目描述约翰的N(l<N<50000)头奶牛实在是太难伺候了，她们甚至有自己独特的产奶时段.当然对于某一头奶牛，她每天的产奶时段是固定的，为时间段A到B包括时间段A和时间段B.显然，约翰必须开发一个调控系统... 查看详情

usaco2002feb奶牛自行车队

【USACO2002Feb】奶牛自行车队TimeLimit:1000msMemoryLimit:131072KBytesDescriptionN头奶牛组队参加自行车赛。车队在比赛时排成一列，需要绕场S圈。由于空气阻力的作用，领队奶牛消耗的体力要比后面的多。每头奶牛的初始体力都是相同的，... 查看详情

bzoj2590[usaco2012feb]cowcoupons*

bzoj2590[Usaco2012Feb]CowCoupons题意：市场上有N头奶牛，第i头奶牛价格为Pi。FJ有K张优惠券，使用优惠券购买第i头奶牛时价格会降为Ci，每头奶牛只能使用一次优惠券。FJ想知道花不超过M的钱最多可以买多少奶牛。n≤50000，m≤10^14。题... 查看详情

洛谷p3663[usaco17feb]whydidthecowcrosstheroadiiis

P3663[USACO17FEB]WhyDidtheCowCrosstheRoadIIIS题目描述Whydidthecowcrosstheroad?Well,onereasonisthatFarmerJohn‘sfarmsimplyhasalotofroads,makingitimpossibleforhiscowstotravelaroundwithoutcrossingmanyofthem.为 查看详情

bzoj3062[usaco2013feb]taxi*

bzoj3062[Usaco2013Feb]Taxi题意：Bessie在农场上为其他奶牛提供出租车服务，她必须赶到这些奶牛的起始位置，并把他们带到它们的目的地。Bessie的车很小，所以她只能一次只能搭载一头奶牛。N只奶牛的起始位置和结束为止都是已知的... 查看详情

bzoj1782[usaco2010feb]slowdown慢慢游*

bzoj1782[Usaco2010Feb]slowdown慢慢游题意：n只奶牛各有一个目的地。它们按顺序从根节点到达自己的目的地，如果当前奶牛经过了其它已经到达的奶牛的目的地，就要放慢一次脚步。求每只奶牛要放慢多少次脚步。n≤100000。题解：对... 查看详情

bzoj3446[usaco2014feb]cowdecathlon*

bzoj3446[Usaco2014Feb]CowDecathlon题意：FJ有n头奶牛。FJ提供n种不同的技能供奶牛们学习，每头奶牛只能学习一门技能，每门技能都要有奶牛学习。第i头奶牛学习第j门技能，FJ得到的分数S[i][j]。此外还有b个奖励，第i个奖励的格式是：P... 查看详情

洛谷p3048[usaco12feb]牛的idcowids

P3048[USACO12FEB]牛的IDCowIDs题目描述Beingasecretcomputergeek,FarmerJohnlabelsallofhiscowswithbinarynumbers.However,heisabitsuperstitious,andonlylabelscowswithbinarynumbersthathaveexactlyK"1"bits(1<=K< 查看详情