OR115. 小明卖食物
描述
小明有n(1≤n≤2000)个美味的食物,他想卖掉它们来赚钱。这些食物放在一些箱子里,它们有些有趣的特性:
(1)这些食物被编号1~n,每一天小明可以从这排箱子的头部或者尾部取出食物去卖;
(2)这些食物放的越久,年龄越大,价值越大,食物i有一个初始的价值V(i);
(3)放了a天后,年龄为a,食物最终价值为V(i)xa。
给定每一个食物的初始价值V(i),请求出小明卖掉它们后可以获得的最大价值,第一天出售的食物年龄为1,此后每增加一天食物的年龄就加1。
输入描述
第1行:一个整数n;输出描述
1行:小明最终可以获得的最大价值。示例1
输入:
5 1 3 1 5 2
输出:
43
说明:
小明出售这些食物(初始价值1,3,1,5,2)的顺序为:第一天卖掉1个,第二天卖掉5个,第三天卖掉2个,第四天卖掉3个,第五天卖掉4个,获得最大的价值1x1+2x3+3x3+4x1+5x5=43。C 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2020-04-22
#include<stdio.h> int main(){ int n,i,j,k=1,sum=0; scanf("%d",&n); int v[n]; for(i=0;i<n;i++) scanf("%d",&v[i]); i=0;j=n-1; while(i<j){ if(v[i]<v[j]){ sum=sum+v[i]*k; i++; } else{ sum=sum+v[j]*k; j--; } k++; } sum=sum+v[i]*k; printf("%d",sum); return 0; }
C 解法, 执行用时: 2ms, 内存消耗: 372KB, 提交时间: 2020-07-29
#include<stdio.h> main() { int Num,i; while(~scanf("%d",&Num)) { int V[Num]; for(i=0;i<Num;i++) scanf("%d",&V[i]); int day=1; int remain=Num; int upper=0,lower=Num-1; int sum=0; while(remain>0) { if(V[upper]<V[lower]) { sum+=V[upper]*day; upper++; } else { sum+=V[lower]*day; lower--; } remain--; day++; } printf("%d\n",sum); } }