最小愤怒值之和：CC酒店客房分配问题 - 动态规划解法

首先，我们需要将问题抽象为一个图论问题。将每个房间看作图中的一个节点，如果两个房间相邻，则在它们之间添加一条边。我们的目标是找到一个最小权重的环，使得环中的节点数量等于n。\n\n我们可以使用动态规划来解决这个问题。定义dp[i][j]表示前i个房间中，选择j个房间形成的环的最小愤怒值之和。\n\n我们可以根据最后一个房间的选择来进行状态转移。假设最后一个房间选择的是第k个房间，则前i个房间形成的环的最小愤怒值之和可以通过dp[i-1][j-1] + w[k]来计算，其中w[k]表示第k个房间的愤怒值。我们需要选择一个最小的愤怒值。\n\n因此，我们可以得到状态转移方程：\n\ndp[i][j] = min(dp[i-1][j-1] + w[k])，其中1 ≤ k ≤ m\n\n最终的答案就是dp[n][n]。\n\n下面是完整的C++代码：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <climits>\n\nusing namespace std;\n\nconst int MAXN = 105;\nconst int INF = INT_MAX;\n\nint dp[MAXN][MAXN];\n\nint main() {\n int n, m;\n cin >> n >> m;\n\n vector<int> w(m + 1);\n for (int i = 1; i <= m; i++) {\n cin >> w[i];\n }\n\n // 初始化dp数组\n for (int i = 0; i <= n; i++) {\n for (int j = 0; j <= n; j++) {\n dp[i][j] = INF;\n }\n }\n dp[0][0] = 0;\n\n // 动态规划计算dp数组\n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= min(i, m); j++) {\n for (int k = 1; k <= m; k++) {\n dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + w[k]);\n }\n }\n }\n\n // 找到最小愤怒值之和\n int minAngry = INF;\n for (int k = 1; k <= m; k++) {\n minAngry = min(minAngry, dp[n][k]);\n }\n\n cout << minAngry << endl;\n\n return 0;\n}\n\n\n该算法的时间复杂度为O(n * m^2)，其中n为客人数量，m为房间数量。