算法
(线性DP) O(n2)
题意:
你想保证 n 年中你都有一台电脑,一开始你有一台。
如果你在第 y(1⩽ 年购买了一台电脑,那么你需要花费 c 的代价。
如果你这台电脑一直用到了第 z 年,在第 z 年又买了一台新的,你需要支付 m(y, z) 的维修费用。
给定 n,c,数组 m。求最小花费。
首先划分阶段。
每一年可以划分为一个阶段。
f[i]
表示直到第 i 年 f[0], f[1], \cdots, f[i - 1] 你手里都有一台电脑的最小花费。
f[i]
需要从 f[j]
转移过来。
如何转移?
枚举上一次买电脑是哪一年!
假设上一次买电脑是第 j 年
那么 1 \sim j - 1 年就是一个子问题,我们已经算出了 f[j - 1] 是满足这个子问题的最优解,后面我们就不用考虑前 j - 1 年的情况,且它也不会影响我们后面的决策。
第 j 年到第 i 年的维修费用是 m(j, i),花费是 c
因此可以用 f[j - 1] + m(j, i) + c 来更新 f[i]
f[i] = min\{f[j - 1] + m(j, i) + c | 1 \leqslant j \leqslant i\}
边界条件:
f[0] = 0
f[1], f[2], \cdots, f[n] 一开始都应该初始化为 +\infty
C++ 代码
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int c, n;
int m[1010][1010], f[1010];
int main() {
while (cin >> c >> n) {
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
cin >> m[i][j];
}
}
memset(f, 0x3f3f, sizeof(f));
f[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
f[i] = min(f[i], f[j - 1] + m[j][i] + c);
}
}
cout << f[n] << '\n';
}
return 0;
}