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

うちぱらららららr

プログラミングやその周辺のことを主に書きます。

AOJ-0611 Silk Road

シルクロード | Aizu Online Judge


再帰の練習のためにメモ化再帰で解きました.

問題概要

N+1の都市があり,M日以内に都市0から都市Nに移動する.
移動するときに 天候C[i] * 都市間の距離D[j] の疲労度が溜まっていきそれが最小になるように移動していく.

解法

メモ化再帰をする.

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
 
#define int long long
 
int n, m;
int d[1010], c[1010];
int dp[1010][1010];
 
int rec(int x, int y)
{
  if (dp[x][y] != -1) return dp[x][y];
   
  int res = 0;
   
  if (x == n) res = 0;
  else if (y == m) res = 198298398;
  else res = min(rec(x + 1, y + 1) + d[x] * c[y], rec(x, y + 1));
 
  return dp[x][y] = res;
}
 
signed main(void)
{
  cin >> n >> m;
  rep(i, n) cin >> d[i];
  rep(i, m) cin >> c[i];
 
  memset(dp, -1, sizeof(dp));
 
  cout << rec(0, 0) << endl;
 
  return 0;
}

dpできない