PKU-3186: Treats for the Cows

keyword

メモ化再帰　C

問題概要

dequeに配列(長さN<2000)が詰まっている。i番目に取り出した要素をv_iとしたとき、Σ i*v_iを最大化する問題。

解法

Greedyでは駄目らしい。のでメモ化再帰して解く。memo[from][to]は[from, to)が残ったときに得られる最大値。計算量O(N^2)。

long long memo[2002][2002];
int as[2002];
int N;

long long max(long long a, long long b){ return a>b?a:b; }

long long solve(int from, int to){
    int day = N - (to - from) + 1;
    if(memo[from][to]) return memo[from][to];
    if(day==N)
        return memo[from][to] = N*as[from];
    return memo[from][to] = max(solve(from+1,to)+day*as[from], solve(from,to-1)+day*as[to-1]);
}

main(){
    int i;
    scanf("%d",&N);
    for(i=0;i<N;i++)
        scanf("%d",as+i);
    printf("%lld\n",solve(0,N));
}