欢迎访问我的博客：blog.chungzh.cn

P3399 丝绸之路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

分析

简单的动态规划题。

一步到位，用一维的 dp。设 $f[j]$ 表示到达第 $j$ 个城市所需的最小花费，假设第 $i$ 天到达，有状态转移方程：

$$ f[j] = \min(f[j], f[j - 1] + d[j] * c[i]); $$

然后我们在外层循环枚举 $i$，然后里层 $j$ 从大到小循环即可。

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;
const int MAXN = 1005;
int n, m;
int c[MAXN], d[MAXN];
int f[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) { cin >> d[i]; }
  for (int i = 1; i <= m; i++) { cin >> c[i]; }
  memset(f, -1, sizeof f);
  f[0] = 0;
  for (int i = 1; i <= m; i++) {
    for (int j = n; j >= 1; j--) {
      if (f[j - 1] == -1) continue;
      if (f[j] == -1) {
        f[j] = f[j - 1] + d[j] * c[i];
      } else {
        f[j] = min(f[j], f[j - 1] + d[j] * c[i]);
      }
    }
  }
  cout << f[n] << endl;
  return 0;
}