Algorithm

problem link- https://www.spoj.com/problems/TRT/

TRT - Treats for the Cows

#dynamic-programming

 

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

The maximum revenue FJ can achieve by selling the treats

Example

Input:
5
1
3
1
5
2

Output:
43

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>

using namespace std;
int n=0;
int dp[2001][2001];
int a[2001];


long long calc(int i,int j){
	long long inc=i+(n-1)-j+1;
	if(i==j)return inc*a[j];
	if(dp[i][j]!=-1)return dp[i][j];
	return dp[i][j]=max((inc*a[i]+calc(i+1,j)),(inc*a[j]+calc(i,j-1)));
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			dp[i][j]=-1;
		}
	}
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	printf("%lld\n",calc(0,n-1));
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5
1
3
1
5
2

Output

x
–
+
cmd
43
Advertisements

Demonstration

SPOJ Solution-Treats for the Cows-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python