[AOJ] No. 0611 シルクロード (Silk Road)

2019年11月3日2019年11月11日

問題

方針

都市 \( i \ (1 \leq i \leq N)\) に到達して滞在する可能性のある日 \( j \) の範囲は、\( i \leq j \leq M – N + i\) となります。ここで、次の配列を考えます。\( d(i, j) \) を \( j \) 日に都市 \( i \) に到達したときの疲労度の最小値とします。この配列の更新は、

\[d(i + 1, j + 1) = \min(d(i + 1, j + 1), D_iC_j + \min \{ d(i, j), j = i, i + 1, \cdots , M – N + i\})\]

となります。答えは、\( \min \{ d(N, i), i = N, N + 1, \cdots, M\} \) となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define n 1001

ll dp[n][n]{};

int main() {
    int N, M;
    cin >> N >> M;
    ll D[N], C[M];
    
    for (int i = 0; i < N; i++) {
        cin >> D[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> C[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = 1000000000000;
        }
    }
    dp[0][0] = 0;
    for (int i = 0; i < N; i++) {
        ll v = 1000000000000;
        for (int j = i; j <= M - N + i; j++) {
            v = min(v, dp[i][j]);
            dp[i + 1][j + 1] = min(dp[i + 1][j + 1], v + D[i] * C[j]);
        }
    }
    ll ans = dp[N][M];
    for (int i = N; i < M; i++) {
        ans = min(ans, dp[N][i]);
    }
    cout << ans << "\n";
    return 0;
}