POJ 3186 - Treats for the Cows

http://poj.org/problem?id=3186

概要

おやつが \(N\) 個一直線上に並んでおり、毎日どちらかの端のおやつを取り出す。 \(i\) 番目のおやつを \(a\) 日目に取り出したとき、\(v(i) \cdot a\) の利益を得る。 すべてのおやつを取り除いた後、得られる利益の最大値を答える。

制約

• \(1 \le N \le 2000\)
• \(1 \le v(i) \le 1000\)

解法

ある区間のおやつを最適に取り除いたときの利益をメモ化しながら計算する。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int N;
 6 int v[2000];
 7 
 8 int memo[2000][2000];
 9 int solve(int beg, int end)
10 {
11   int& ans = memo[beg][end];
12   if (ans) {
13     return ans;
14   }
15   const int age = N - (end - beg);
16   if (beg == end) {
17     return ans = v[beg] * age;
18   } else {
19     return ans = max(v[beg] * age + solve(beg+1, end), v[end] * age + solve(beg, end-1));
20   }
21 }
22 
23 int main()
24 {
25   scanf("%d", &N);
26   for (int i = 0; i < N; i++) {
27     scanf("%d", &v[i]);
28   }
29   printf("%d\n", solve(0, N-1));
30   return 0;
31 }