Description
FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time.
The treats are interesting for many reasons:
- The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats.
- Like fine wines and delicious cheeses, the treats improve with age and command greater prices.
- The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000).
- Cows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a.
Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally?
The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.
Input
Line 1: A single integer, N
Lines 2..N+1: Line i+1 contains the value of treat v(i)
Output
Line 1: The maximum revenue FJ can achieve by selling the treats
Sample Input
5
1
3
1
5
2
Sample Output
43 题意：
可以从数组的左右两端拿数字，权值依次上升，求权值乘上数字的和的最大值。
思路：
dp[i][j]表示起点为i,终点为j的组数，可以得到的最大值是多少。
首先枚举长度，再计算该长度所有的dp[i][j]的值。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 2.1e9;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-);
int num[];
int dp[][];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&num[i]);
}
for(int i=;i<=n;i++){
dp[i][i]=num[i]*n;
}
for(int len=;len<=n;len++){
for(int i=;i<=n;i++){
int j=i+len-;
if(j<=n)dp[i][j]=max(dp[i][j],dp[i][j-]+num[j]*(n-len+));
j=i-len+;
if(j>=)dp[j][i]=max(dp[j][i],dp[j+][i]+num[j]*(n-len+));
}
}
printf("%d\n",dp[][n]);
return ;
}