aoj 0611 - Silk Road

問題

問題概要

都市0から都市Nへ移動する。都市iから都市i+1にj日目に移動するとき，Di*Cj疲労度がたまる。都市0から都市Nまで移動した時の疲労度の最小を求めよ．ただしM日以内にNに到達しなければならない。

解法

都市iにいて，その時j日目の状態において，そこから先の移動方法を考えるにあたってそれ以前の移動方法は関係ないので、dp[どこのて地点にいるか][何日目] = (疲労度の最小値)の要素をdpで埋めていけばいい。 漸化式は
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j - 1] + d[i - 1] * c[j])
で、j日目に動かないでi地点にいる時と、j日目に動いてi地点に到達する時の疲労度の最小値を採用すればいい。初期値は*日目に0地点にいるものは疲労度は0で他のものは最小値を求めるので、大きな値で初期化しておけばいい。答えは、M日目までにN地点に到達したものの中で最小のものを選択すればいい。

ミス

特になし。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
static const int INF = 1e9;

int main(void){
    int n, m; cin >> n >> m;
    vector<int> d(n);
    rep(i, n) cin >> d[i];
    vector<int> c(m);
    rep(i, m) cin >> c[i];
    //dp[どこの地点にいるか][何日目]
    int dp[1001][1001];
    rep(i, 1001)rep(j, 1001) dp[i][j] = INF;//初期化
    rep(i, m) dp[0][i] = 0;//初期化
    reps(i, 1, n + 1){
        rep(j, m){
            //漸化式
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j - 1] + d[i - 1] * c[j]);
        }
    }
    int ans = INF;
    //さらに最小の答えを探す
    rep(i, m){
        ans = min(ans, dp[n][i]);
    }
    printf("%d\n", ans);
    return 0;
}