解いた問題のソースコードと解説など。


POJ 3186 Treats for the Cows

問題文

DP強化週間。

配列が与えられ、毎ターン配列の先頭か最後尾から数字を取り出せる。Tターン目に取り出した数字がaだとすると得点T * a が得られる。全ての数字を取り出したときの最大の得点を求める問題。

下の図のように
f:id:Area1:20130220182919p:plain:w200
dp[i][j]:=(配列の左からi個、右からj個取り出したときの最大の得点)でDPする。
そうすると

	dp[i][j] = max(dp[i - 1][j] + 左から取り出した得点,
		               dp[i][j - 1] + 右から取り出した得点);

になる。左から(もしくは右から)は全く取り出さないケースに注意。

以下ソース。

int dp[2001][2001];
int v[2001];

int main(int argc, char **argv){
  memset(dp, 0, sizeof(dp));
  int n;
  cin >> n;
  for(int i = 0; i < n; i++) cin >> v[i];

  dp[0][1] = v[n - 1];
  dp[1][0] = v[0];

  for(int i = 0; i <= n; i++){
    for(int j = 0; i + j <= n; j++){
      if(i - 1 < 0){
	dp[i][j] = (i + j) * v[n - j] + dp[i][j - 1];
      }else if(j - 1 < 0){
	dp[i][j] = (i + j) * v[i - 1] + dp[i - 1][j];
      }else{
	dp[i][j] = max((i + j) * v[i - 1] + dp[i - 1][j],
		       (i + j) * v[n - j] + dp[i][j - 1]);
      }
    }
  }

  int ans = 0;
  for(int i = 0; i < n; i++)
    ans = max(ans, dp[i][n - i]);

  cout << ans << endl;
  return 0;
}

TopCoderの方の調子が悪い。

しょげないでよBaby 眠れば治る