P3399 丝绸之路
Zirnc
2022-08-25 20:40:45
欢迎访问我的博客：[blog.chungzh.cn](https://blog.chungzh.cn)
[P3399 丝绸之路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P3399)
## 分析
简单的动态规划题。
一步到位，用一维的 dp。设 $f[j]$ 表示到达第 $j$ 个城市所需的最小花费，假设第 $i$ 天到达，有状态转移方程：
$$
f[j] = \min(f[j], f[j - 1] + d[j] * c[i]);
$$
然后我们在外层循环枚举 $i$，然后里层 $j$ 从大到小循环即可。
```cpp
#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;
}
```