Treats for the Cows

문제 설명

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 

Hint

Explanation of the sample:
Five treats. On the first day FJ can sell either treat #1 (value 1) or treat #5 (value 2).
FJ sells the treats (values 1, 3, 1, 5, 2) in the following order of indices: 1, 5, 2, 3, 4, making 1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.

Source

테스트 입력
기대 출력
시간 제한
메모리 제한
추가 프로세스
테스트 용례 1
텍스트로 표시
5↵
1↵
3↵
1↵
5↵
2↵
텍스트로 표시
43↵
1초
64M
0
문제풀이의 방향.
제목과 같은 의미:
숫자 서열을 제시한 다음에 매번 대열의 첫 번째 또는 대열의 끝에서만 해당하는 숫자를 추출하고 횟수를 곱할 수 있다. 몇 번째 추출한 원소는 몇 곱하기 몇 다음에 모든 곱하기 후의 원소를 합쳐서 가장 큰 합을 구한다.
대략적인 사고방식:
처음에는 이 문제가 욕심 문제인 줄 알았는데, 사례에 대한 욕심 알고리즘이 완전히 일치했기 때문이다.그러나 제출한 후에 잘못된 것을 발견했다. 예를 들어 이런 용례가 8197이다. 욕심의 사고방식에 따르면 7*1+8*2+1*3+9*4=62이다. 그러나 이렇게 9*4+7*3+1*2+8*1=67로 가면 욕심이 얻은 결과가 틀린 것이 분명하기 때문에 동태적인 기획 방법을 이용하여 계산해야 한다.우리는 내부에서 밖으로 나가는 사고방식을 이용하여 계산을 할 수 있다. 시작할 때 모든 숫자가 마지막에 꺼질 수 있다고 가정한 다음에 순서대로 동적 계획을 이용하여 계산을 하고 매번 비교 전후에 상응하는 횟수의 결과의 최대치를 곱하여 그 상태를 부여할 수 있다.마지막으로 dp[1][n]을 출력하면 됩니다.
구체적인 실현:
먼저 주어진 숫자를 하나의 수조에 저장한 다음에 2차원 수조를 정의하여 해당하는 상태를 표시하고 해당하는 횟수를 기록할 때 얻은 최대 값을 기록한다.시작할 때 모든 숫자가 마지막에 꺼질 수 있다고 가정한 다음에 이중 순환을 이용하여 이것에 따라 안에서 밖으로 밀면 된다.
참고 사항:
(1) 숫자 서열의 길이가 비교적 크기 때문에 정의된 수조는 전역 변수로 삼아야 한다. 그렇지 않으면re가 된다.
(2) 상태 이동 방정식은 수조의 하표를 주의하고 수조의 하표 변환을 주의한다.
(3) 마지막 출력을 주의하고 자신의 상태에 따라 그에 상응하는 값을 출력한다.
구현 코드

<span style="font-family:Microsoft YaHei;font-size:14px;">#include<stdio.h>
#include<string.h>
int dp[2005][2005];
//int max(int x,int y)
//{
//	if(x>y)
//	return x;
//	return y;
//}
int main()
{
   int n,i,p,j;
   int jiazhi[2005];
   int temp1,temp2; 
    memset(dp,0,sizeof(dp));
   scanf("%d",&n);
       for(i=0;i<n;i++)
         {
             scanf("%d",&jiazhi[i]);
               dp[i][i]=jiazhi[i]*n;
         }
        for(p=1;p<=n;p++)
       {
           for(i=0;i<n-p;i++)
             {
                 j=i+p;
                 temp1=dp[i+1][j]+jiazhi[i]*(n-j+i);
                 temp2=dp[i][j-1]+jiazhi[j]*(n-j+i);
                // dp[i][j]=max(dp[i+1][j]+jiazhi[i]*(n-j+i),dp[i][j-1]+jiazhi[j]*(n-j+i));
                if(temp1>temp2)
                {
                	dp[i][j]=temp1;
                }
                else
                {
                	dp[i][j]=temp2;
                }
            }
       }
        printf("%d
",dp[0][n-1]);
   
   return 0;
}</span>