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; }