算法

(线性DP) $O(n^2)$

题意：

你想保证 $n$ 年中你都有一台电脑，一开始你有一台。
如果你在第 $y(1 \leqslant y \leqslant n)$ 年购买了一台电脑，那么你需要花费 $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;
}