forked from Ouditchya/SPOJ
-
Notifications
You must be signed in to change notification settings - Fork 0
/
TRT.cpp
76 lines (52 loc) · 1.44 KB
/
TRT.cpp
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// AC, ALGO : Dynamic Programming.
/* Some Helpful Links :
http://compsci.ca/v3/viewtopic.php?t=16847
http://en.wikipedia.org/wiki/Dynamic_programming
http://www.codechef.com/wiki/tutorial-dynamic-programming
http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static
http://www.quora.com/Dynamic-Programming/Are-there-any-good-resources-or-tutorials-for-Dynamic-Programming-besides-TopCoder-tutorial
*/
// For any clarifications, contact me at : [email protected]
#include<cstdio>
#define MAX 2100
using namespace std ;
#define get getchar_unlocked
inline int inp( )
{
int n = 0 , s = 1 ;
char p = get( ) ;
if( p == '-' )
s = -1 ;
while( ( p < '0' || p > '9' ) && p != EOF && p != '-' )
p = get( ) ;
if( p == '-' )
s = -1 , p = get( ) ;
while( p >= '0' && p <= '9' )
{
n = ( n << 3 ) + ( n << 1 ) + ( p - '0' ) ;
p = get( ) ;
}
return n * s ;
}
int treats[MAX] , interval[MAX][MAX] , n ;
inline int max( int a , int b ) { return ( a > b ? a : b ) ; }
int solve( int a , int b )
{
int &ans = interval[a][b] ;
if( ans )
return ans ;
if( a == b )
return n * treats[a] ;
int age = a + n - b ;
ans = max( age * treats[a] + solve( a + 1 , b ) , age * treats[b] + solve( a , b - 1 ) ) ;
return ans ;
}
int main()
{
int i ;
n = inp() ;
for( i = 0 ; i < n ; i++ )
treats[i] = inp() ;
printf("%d\n",solve(0,n)) ;
return 0 ;
}