【题解】P2858 Treats for the Cows

发表于 分类于 阅读次数： Valine：

题目链接（洛谷）

题目大意

约翰购置了\(N(1\le N\le 2000)\)份零食来卖给奶牛们．每天约翰售出一份零食。当然约翰希望这些零食全部售出后能得到最大的收益．这些零食有以下这些有趣的特性：

零食按照\(1…N\)编号，它们被排成一列放在一个很长的盒子里。盒子的两端都有开口，约翰每天可以从盒子的任一端取出最外面的一个。

每份零食的初始价值不一定相同。约翰进货时，第\(i\)份零食的初始价值为\(V_i (1\le V_i\le 1000)\)。这些零食储存得越久就越好吃。当然，这样约翰就可以把它们卖出更高的价钱。第i份零食如果在被买进后的第\(a\)天出售，则它的售价是\(V_i\times a\)。

约翰告诉了你所有零食的初始价值，并希望你能帮他计算一下，在这些零食全被卖出后，他最多能得到多少钱。

分析

设\(dp(i,j)\)为卖出丛\(i\)到\(j\)的物品可以得到的最大值。

转移：

有两种情况可以选，左边取和右边取，易得转移方程：

\(dp(i,j) = \max\{dp(i+1,j)+V_i\times(n-l+1),dp(i,j-1])+V_j*(n-l+1)\}\)

初始化：长度为一的赋值为最后 一个拿的情况：\(dp(i,i) = V_i\times n\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int dp[2004][2005];
int n,v[2004];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i];
        dp[i][i]=v[i]*n;
    }
    for(int l=1;l<=n;l++){
        for(int i=1;i+l-1<=n;i++){
            int j=i+l-1;
            dp[i][j]=max(dp[i+1][j]+v[i]*(n-l+1),dp[i][j-1]+v[j]*(n-l+1));
        }
    }
    cout<<dp[1][n];
    return 0;
}