随机化大法好啊

还是随机大法好啊，状压 DP 还是太吃操作了。

题目分析

容易发现对于所有 $1,2$ 类任务先执行 A 还是 B 都是唯一的，但是对于 $3$ 类任务是需要决策的。显然没有贪心策略（可能有但是笔者太菜想不到）决定 $3$ 类任务是现在机器 A 上执行还是机器 B 上执行，那就直接“随机代替思考”。

确定每个任务先做 A 还是 B 之后还需要每个任务之间的顺序。同样“随机代替思考”，直接随出来一个 $n$ 的全排列。

得到所有任务执行顺序之后还需要算出当前状态下的最小总时间。这个是好求的，这里不细说，读者自行思考。

其实上述策略已经是一个完整的解题步骤了，不过还可以继续优化，也就是一个在随机化题目中非常常见的优化策略“局部搜索”，在当前得到的较优解附近进行搜索。虽然已经不能保证搜到最优解，但一定会比常规做法更快搜到最优解。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
int n;
struct task {
	int t, a, b;
} tsk[25];
int ans = INF;
int calc(int p[]) {
	vector<task> A, B;//分别存储现在A上执行和先在B上执行的任务 
	for (int i = 1; i <= n; i++) {
		int id = p[i];
		if (tsk[id].t == 1) A.push_back(tsk[id]);
		else if (tsk[id].t == 2) B.push_back(tsk[id]);
		else {
			if (rand() & 1) A.push_back(tsk[id]);
			else B.push_back(tsk[id]);
		}
	}
	int ta = 0, tb = 0;
	for (auto x : A) ta += x.a;
	for (auto x : B) {
		tb += x.b;
		if (ta > tb) ta += x.a;
		else ta = tb + x.a;
	}
	int res1 = max(ta, tb);
	ta = tb = 0;
	for (auto x : B) tb += x.b;
	for (auto x : A) {
		ta += x.a;
		if (tb > ta) tb += x.b;
		else tb = ta + x.b;
	}
	int res2 = max(ta, tb);
	//res1和res2其实是两种方案，要么先把A的任务执行完，要么先把B的任务执行完 
	return max(res1, res2);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	mt19937 rand(time(NULL));//随机函数 
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> tsk[i].t >> tsk[i].a >> tsk[i].b;
	int mp[25], p[25], id[25];
	for (int i = 1; i <= n; i++) mp[i] = i;//mp表示当前较优解的执行顺序 
	random_shuffle(mp + 1, mp + n + 1);//打乱 
	while ((double)clock() / CLOCKS_PER_SEC < 0.95) {
		for (int i = 1; i <= n; i++) p[i] = mp[i];
		for (int i = 1; i <= 3; i++) swap(p[rand() % n + 1], p[rand() % n + 1]);
		//在较优解附近搜索 
		int now = calc(p);//计算当前最少总时间 
		if (now < ans) {
			ans = now;
			for (int i = 1; i <= n; i++) mp[i] = p[i];//如果找到了更优解自然要更新 
		}
		
		//下面是局部搜索 尝试交换当前较优解的每一对位置 
		for (int i = 1; i <= n; i++) id[i] = i;
		random_shuffle(id + 1, id + n + 1);//初始化 
		bool flg = 1;
		while (flg) {
			flg = 0;
			for (int i = 1; i < n; i++) {
				for (int j = i + 1; j <= n; j++) {
					int x = id[i], y = id[j];
					swap(p[x], p[y]);//交换 
					int nxt = calc(p);
					if (nxt < ans) {
						ans = now = nxt;
						for (int k = 1; k <= n; k++) mp[k] = p[k];
						flg = 1;
					} else if (nxt < now) {
						now = nxt;
						flg = 1;
					//无论是比ans小还是now小，都代表这次交换一定是不劣的
					//所以flg=1还可以尝试继续交换。 
					} else swap(p[x], p[y]);//否则就换回去 
				}
			}
		}
	}
	cout << ans;
	return 0;
}