P2858 [USACO06FEB] Treats for the Cows G/S

题目描述约翰经常给产奶量高的奶牛发特殊津贴于是很快奶牛们拥有了大笔不知该怎么花的钱。为此约翰购置了 N1≤N≤2000份美味的零食来卖给奶牛们。每天约翰售出一份零食。当然约翰希望这些零食全部售出后能得到最大的收益这些零食有以下这些有趣的特性零食按照 1,…,N 编号它们被排成一列放在一个很长的盒子里。盒子的两端都有开口约翰每天可以从盒子的任一端取出最外面的一个。与美酒与好吃的奶酪相似这些零食储存得越久就越好吃。当然这样约翰就可以把它们卖出更高的价钱。每份零食的初始价值不一定相同。约翰进货时第 i 份零食的初始价值为 Vi​1≤V≤1000。第 i 份零食如果在被买进后的第 a 天出售则它的售价是 Vi​×a。Vi​ 表示的是从盒子顶端往下的第 i 份零食的初始价值。约翰告诉了你所有零食的初始价值并希望你能帮他计算一下在这些零食全被卖出后他最多能得到多少钱。输入格式第一行一个正整数 N。接下来 2∼N1 行第 i1 行为一个正整数 Vi​。输出格式一行一个整数表示答案。输入输出样例输入 #1复制5 1 3 1 5 2输出 #1复制43说明/提示样例的最优解是按 1→5→2→3→4 的顺序卖零食得到的钱数是 1×12×23×34×15×543。代码DFS#include bits/stdc.h using namespace std; int v[2005],n; int ans; void DFS(int day,int shang,int xia,int jia){ if(shangxia){ ansmax(ans,jiav[shang]*day); return; } DFS(day1,shang1,xia,jiaday*v[shang]); DFS(day1,shang,xia-1,jiaday*v[xia]); } int main(){ cinn; for(int i1;in;i){ cinv[i]; } DFS(1,1,n,0); coutans; return 0; }代码DP#includebits/stdc.h using namespace std; const int N2005; int n,dp[N][N],v[N]; int main(){ cinn; for(int i1;in;i){ cinv[i]; } for(int i1;in;i){ for(int jn;ji;j--){ int an-(j-i1); dp[i][j]max(dp[i-1][j]v[i-1]*a,dp[i][j1]v[j1]*a); } } int maxn0; for(int i1;in;i){ maxnmax(maxn,dp[i][i]v[i]*n); } coutmaxn; return 0; }