Algoogle

Algorithm for Programming Contest

AOJ 0611 Silk Road

Category: AOJ Tag: dp

Silk Road

問題概要


都市0から都市N(<=1000)へ移動したい.
都市iから都市i+1にj日目に移動するとき,だけ疲労度がたまる.
M(<=1000)日以内に移動するとき,都市0から都市Nまで移動した時の疲労度の最小を求めよ.

解法


DPします.
dp[i][j] := 都市iにj日目にいる時の疲労度の最小

コード


(0611.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repi(i,0,n)

inline void chmin(int &x, int y) { x = min(x,y); }
const int inf = 1e9;
int n, m, d[1024], c[1024], dp[1024][1024];

int solve() {
    rep(i,n+1) rep(j,m+1) dp[i][j] = inf;
    dp[0][0] = 0;
    rep(i,n) rep(j,m) {
        chmin(dp[i][j+1], dp[i][j]);
        chmin(dp[i+1][j+1], dp[i][j]+d[i]*c[j]);
    }
    return *min_element(dp[n], dp[n]+m+1);
}

void input() {
    cin >> n >> m;
    rep(i,n) cin >> d[i];
    rep(i,m) cin >> c[i];
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << fixed << setprecision(12);
    input();
    cout << solve() << endl;
    return 0;
}

Comments