链家2018链习生招聘考试-编程题三

发表于 | 分类于 ，

题目

描述

小明有 n( 1<=n<=2000 )个美味的食物,他想卖掉它们来赚钱.
这些食物放在一些箱子里,他们有些有趣的特性
1. 这些食物被编号为 1~n,每一天小明可以从这些箱子的头部或者尾部取出食物去卖
2. 这些食物放得越久,年龄越大,价值越大,食物 i 有一个出事的价值 v(i)
3. 放了 a 天后年龄为 a ,食物最终价值为 v(i)*a
给定每一个食物的初始价值v(i),请求出小明卖掉它们后可以获得的最大价值,
第一天出售的食物的年龄为 1,此后每增加一天食物的年龄就加 1

输入

第 1 行:一个整数 n
第 2 到第 n+1 行:每个食物的初始价值 v

输出

1 行:小明最终可以获得的最大价值

Example

Input

5
1
3
1
5
2

Output

43

题解

动态规划

  • 定义 income(i,j) 为已经卖出除编号 i 到 j 之外的食物,所得到的最大价值
  • income(i,i) 中最大值即为所求
  • 可以优化空间复杂度 O(n*n) 为 O(n)
  • 状态转移方程:( day 为卖出除编号 i 到 j 之外的食物所用的时间 )
1
income( i,j )=max( income( i-1,j )+food[i-1]*day,income( i,j+1 )+food[j+1]*day )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>

using namespace std;

int n,food[2002],income[2002],day,maxIncome;

int main()
{
    memset(income,0,sizeof income);
    maxIncome=0;
    cin>>n;
    food[0]=food[n+1]=0;
    for(int i=1;i<=n;++i)
    {
        cin>>food[i];
    }
    for(int i=1;i<=n;++i)
    {
        day=i-1;
        for(int j=n;j>=i;--j)
        {
            income[j]=max(income[j]+food[i-1]*day,income[j+1]+food[j+1]*day);
            ++day;
        }
        maxIncome=max(maxIncome,income[i]+food[i]*n);
    }
    cout<<maxIncome;
}