読者です 読者をやめる 読者になる 読者になる

AOJ0611 - Silk Road (DP)

AOJ0611のSilk RoadをDPの練習として解いてみました.
また,この問題を解くにあたって以下のサイトを参考にしました.

コード

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
#define MAX_D (1000)
#define MAX_C (1000)
 
int N, M;
int D[MAX_D], C[MAX_C];
// -1ならまだ調べていない
int dp[MAX_D + 1][MAX_C + 1];
 
int rec_dp(int now, int day);
 
int main()
{
  scanf("%d%d", &N, &M);
  memset(dp, -1, sizeof(dp)); // -1でメモ化テーブルを初期化
 
  for (int i = 0; i < N; i++) scanf("%d", &D[i]);
  for (int i = 0; i < M; i++) scanf("%d", &C[i]);
 
  printf("%d\n", rec_dp(0, 0));
 
  return (0);
}

// nowは現在地,dayは何日目かを表す
int rec_dp(int now, int day)
{
  if (dp[now][day] != -1){ // 一度調べていたら再利用
    return (dp[now][day]);
  }
   
  int res;
  if (now == N){ // 目的地に到着
    res = 0;
  }
  else if (N - now == M - day){ // 目的地に到着するためには進むしかない場合
    res = rec_dp(now + 1, day + 1) + (D[now] * C[day]);
  }
  else { // 進むか待機するか決められる場合
    res = min(rec_dp(now, day + 1), rec_dp(now + 1, day + 1) + (D[now] * C[day]));
  }
 
  dp[now][day] = res; // 結果を保存
 
  return (dp[now][day]);
}

提出したやつ

今回はメモ化再帰のDPで解きました.
またmemsetを初めて使ってみました.(31行目がdp[now][day] != 0でもいけそう)
単純な再帰に手を加えると計算効率がだいぶ上がるので,マスター出来るようにしたい.
また,漸化式を用いたDPも出来るようになりたい.(forだけで書けるので見た目もタイプ量も減りそう)
もっとこここうした方がいいよ,などあればコメント等に書いて頂ければ幸いです.

(この記事はictechの「Markdown超入門」を受け,Markdownで書かれています)