列表

详情


OR115. 小明卖食物

描述

小明有n(1n≤2000)个美味的食物,他想卖掉它们来赚钱。这些食物放在一些箱子里,它们有些有趣的特性:

(1)这些食物被编号1~n,每一天小明可以从这排箱子的头部或者尾部取出食物去卖;

(2)这些食物放的越久,年龄越大,价值越大,食物i有一个初始的价值V(i);

(3)放了a天后,年龄为a,食物最终价值为V(i)xa。

给定每一个食物的初始价值V(i),请求出小明卖掉它们后可以获得的最大价值,第一天出售的食物年龄为1,此后每增加一天食物的年龄就加1。

输入描述

第1行:一个整数n;

第i+l行:每行食物i的初始价值V(i)。

输出描述

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);
	}
 } 

上一题