题目解析

这道题目要求我们计算在n年期间使用电脑的最小总成本，包括购买新电脑的固定费用和每年的维护费用。我们需要找到一个最优的电脑更换策略，使得总成本最低。

问题分析

1. 输入：

   • 固定费用c：购买新电脑的费用。
   • 年数n：计划使用电脑的总年数。
   • 维护费用矩阵cost[i][j]：表示从第i年开始使用电脑，到第j年的总维护费用。

2. 输出：

   • 最小总成本：在n年期间使用电脑的最小总费用。

3. 关键点：

   • 每次购买新电脑需要支付固定费用c。
   • 维护费用取决于电脑的使用年限。

解题思路

1. 动态规划：

   • 使用动态规划来记录每年更换电脑的最小成本。
   • 定义dp[i]表示前i年的最小总成本。

2. 状态转移：

   • 对于每一年i，考虑从第j年开始使用新电脑（j ≤ i），并计算从第j年到第i年的总成本。
   • 总成本包括：前j-1年的最小成本dp[j-1]、购买新电脑的费用c、以及从第j年到第i年的维护费用cost[j][i-j+1]。
   • 更新dp[i]为所有可能的j中的最小值。

3. 初始化：

   • dp[0] = 0：表示0年的成本为0。
   • 其他dp[i]初始化为一个较大的值（如INF），表示初始状态未知。

4. 结果：

   • dp[n]即为n年期间的最小总成本。

算法步骤

1. 读取输入：

   • 读取固定费用c和年数n。
   • 读取维护费用矩阵cost[i][j]，其中i表示起始年份，j表示使用年限。

2. 初始化dp数组：

   • 将dp数组初始化为一个较大的值，表示初始状态未知。
   • 设置dp[0] = 0。

3. 动态规划计算：

   • 对于每一年i（从1到n）：
     • 对于每一个可能的起始年份j（从1到i）：
       • 计算从第j年开始使用新电脑的总成本：dp[j-1] + c + cost[j][i-j+1]。
       • 如果该成本小于当前的dp[i]，则更新dp[i]。

4. 输出结果：

   • 打印dp[n]，即n年期间的最小总成本。

复杂度分析

• 时间复杂度：O(n²)，因为需要遍历每一年和每一个可能的起始年份。
• 空间复杂度：O(n)，用于存储dp数组。

示例解析

输入：

3
3
5 7 50
6 8
10

解释：

• 固定费用c=3，年数n=3。
• 维护费用矩阵：
  • 第一台电脑：m(1,1)=5，m(1,2)=7，m(1,3)=50。
  • 第二台电脑：m(2,1)=6，m(2,2)=8。
  • 第三台电脑：m(3,1)=10。

计算过程：

1. dp[0] = 0。
2. dp[1] = min(dp[0] + c + cost[1][1]) = 0 + 3 + 5 = 8。
3. dp[2] = min(dp[0] + c + cost[1][2], dp[1] + c + cost[2][1]) = min(0+3+7=10, 8+3+6=17) = 10。
4. dp[3] = min(dp[0] + c + cost[1][3], dp[1] + c + cost[2][2], dp[2] + c + cost[3][1]) = min(0+3+50=53, 8+3+8=19, 10+3+10=23) = 19。

输出：

19

标程

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int MAXN = 5015;

int c, n;
int cost[MAXN][MAXN];
int dp[MAXN];

int main() {
	while (scanf("%d%d", &c, &n) != EOF) {
		// 读取成本矩阵
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n - i + 1; ++j) {
				scanf("%d", &cost[i][j]);
			}
		}
		
		// 初始化dp数组
		memset(dp, INF, sizeof(dp));
		dp[0] = 0;
		
		// 动态规划计算最小成本
		for (int i = 1; i <= n; ++i) {
			for (int j = i; j <= n; ++j) {
				if (dp[i-1] + c + cost[i][j-i+1] < dp[j]) {
					dp[j] = dp[i-1] + c + cost[i][j-i+1];
				}
			}
		}
		
		printf("%d\n", dp[n]);
	}
	return 0;
}