1 条题解
-
0
欢迎访问我的博客:blog.chungzh.cn
P3399 丝绸之路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
分析
简单的动态规划题。
一步到位,用一维的 dp。设 表示到达第 个城市所需的最小花费,假设第 天到达,有状态转移方程:
然后我们在外层循环枚举 ,然后里层 从大到小循环即可。
#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; }
- 1
信息
- ID
- 2335
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者