解题思路

问题分析

我们需要找到完成所有工作的最优顺序，使得总成本最小。每个工作的成本包括基础价格和附加费，附加费取决于之前完成的工作。具体来说：

• 每个工作有一个基础价格。
• 如果工作j在工作i之前完成，那么完成工作i时需要额外支付一个附加费。

方法选择

由于工作数量n最多为14，可以使用状态压缩动态规划（DP）来解决。状态压缩DP通过位掩码来表示已完成的工作集合，从而高效地遍历所有可能的工作顺序。

动态规划状态设计

• 状态表示：使用一个整数mask作为位掩码，其中第i位为1表示工作i已经完成。
• DP数组定义：dp[mask]表示完成mask对应工作的最小总成本。

状态转移

1. 初始化：dp[0] = 0，表示没有工作时成本为0。其他状态初始化为一个大数（INF）。
2. 遍历状态：对于每一个状态mask，遍历所有未完成的工作j。
3. 计算成本：
   • 基础价格：prices[j][j]。
   • 附加费：对于每一个已经完成的工作k（即mask的第k位为1），加上prices[j][k]。
4. 更新状态：将工作j标记为已完成，生成新状态new_mask，并更新dp[new_mask]为更小的成本值。

结果提取

最终结果是dp[(1 << n) - 1]，即所有工作都完成时的最小总成本。

代码步骤详解

1. 输入处理：读取测试用例数量，然后逐个处理每个测试用例。
2. 数据存储：使用二维数组prices存储每个工作的基础价格和附加费。
3. DP数组初始化：dp数组初始化为极大值，dp[0]设为0。
4. 状态转移：
   • 遍历所有可能的状态mask。
   • 对于每个状态，检查所有未完成的工作j。
   • 计算完成工作j的总成本（基础价格 + 附加费）。
   • 更新新状态new_mask的最小成本。
5. 结果输出：输出每个测试用例的最小总成本，格式符合题目要求。

标程

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

const int INF = INT_MAX / 2;

int main() {
	int scenarios;
	cin >> scenarios;
	for (int scenario = 1; scenario <= scenarios; ++scenario) {
		int n;
		cin >> n;
		vector<vector<int> > prices(n, vector<int>(n));
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				cin >> prices[i][j];
			}
		}
		
		int size = 1 << n;
		vector<int> dp(size, INF);
		dp[0] = 0;
		
		for (int mask = 0; mask < size; ++mask) {
			for (int j = 0; j < n; ++j) {
				if (!(mask & (1 << j))) {
					int cost = prices[j][j];
					for (int k = 0; k < n; ++k) {
						if (mask & (1 << k)) {
							cost += prices[j][k];
						}
					}
					int new_mask = mask | (1 << j);
					if (dp[new_mask] > dp[mask] + cost) {
						dp[new_mask] = dp[mask] + cost;
					}
				}
			}
		}
		
		cout << "Scenario #" << scenario << ":" << endl;
		cout << "You have officially been pimped for only $" << dp[size - 1] << endl;
		cout << endl;
	}
	return 0;
}