PKU : 3186 - Treats for the Cows

動的計画法

問題概要

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

N個の自然数からなる数列が入力されます.
先頭か末尾から順番に数字を取っていって, X番目に取った数字には, Xをかけます.
それを足し合わせた値の最大値を出力してください.

アルゴリズム

dp[2002(左側のインデックス)][2002(右側のインデックス)] = 最大の和
となるようにメモ化再帰を行いました.

プログラム

int t[2002];
int dp[2002][2002];

int dfs(int left,int right,int mul){
  if(left == right) return mul*t[left];
  if(dp[left][right] != -1) return dp[left][right];
  return dp[left][right] = max(dfs(left+1,right,mul+1)+mul*t[left],
                               dfs(left,right-1,mul+1)+mul*t[right]);
}

int main(void){
  int n;

  while(scanf("%d",&n) != EOF){
    rep(i,n){
      scanf("%d",&t[i]);
    }

    memset(dp,-1,sizeof(dp));
    printf("%d\n",dfs(0,n-1,1));
  }
}