0w1

JOI 14 予選 Silk Road ( DP )

Silk Road | Aizu Online Judge
dp[ i ]: now on city i, minimum cost

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 3;
const int MAXM = 1e3 + 3;
const int MAXC = 1e3 + 3;
const int MAXD = 1e3 + 3;
const int INF = 0x3f3f3f3f;

void upmin(int &x, int v){ if( x > v ) x = v; }

int n, m;
int d[ MAXN ];
int c[ MAXM ];

int dp[ MAXN ];

void solve(){
    memset( dp, INF, sizeof(dp) );
    dp[ 0 ] = 0;
    for(int i = 0; i < m; ++i)
        for(int j = n - 1; j >= 0; --j){
            upmin( dp[ j + 1 ], dp[ j ] + d[ j ] * c[ i ] );
            // printf("dp[ %d ] <- dp[ %d ] + %d * %d = %d\n", j + 1, j, d[j], c[i],dp[j+1]);
        }
    printf("%d\n", dp[ n ]);
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i)
        scanf("%d", &d[ i ]);
    for(int i = 0; i < m; ++i)
        scanf("%d", &c[ i ]);
    solve();
    return 0;
}