POJ3086 Treats for the Cows(区间DP)

直接区间DP就好了，用记忆化搜索是很方便的。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 #define rep(i,a,b) for(int i(a); i <= (b); ++i)
 9 #define LL  long long
10 
11 
12 
13 const int Q     =    2000        +       10;
14 
15 LL f[Q][Q];
16 LL a[Q];
17 int n;
18 int s[Q];
19 int c[Q][Q];
20 
21 LL dp(int i, int j, LL k){
22     if (i == j) return a[i] * k;
23     if (f[i][j] != -1) return f[i][j];
24     LL ret = -100000000000LL;
25     ret = max(ret, a[i] * k + dp(i + 1, j, k + 1));
26     ret = max(ret, a[j] * k + dp(i, j - 1, k + 1));
27     return f[i][j] = ret;
28 }
29     
30 
31 int main(){
32 
33 
34     while(~scanf("%d", &n)){
35         rep(i, 1, n) scanf("%lld", a + i);
36         memset(f, -1, sizeof f);
37         printf("%lld
", dp(1, n, 1LL));
38     }
39 
40     return 0;
41 
42 }