Untitled

 avatar
user_4230122
c_cpp
a year ago
2.1 kB
6
Indexable
#include <iostream>

using namespace std;
int t, n;
struct node {
	int num_linh, cost;
};
int status[2][22];
node door[21];
int min1;


int totalLinhDeDanh() {
	int total_linh = 0;
	for (int i = 1; i <= n; i++) {
		if (status[1][i] < 3 && status[1][i] >=0 && status[0][i] != 0) {
			total_linh += status[0][i];
		}
	}
	return total_linh;
}
int totalLinhHySinh() {
	int total_linh = 0;
	for (int i = 1; i <= n; i++) {
		if (status[1][i] == -1) {
			total_linh += status[0][i];
		}
	}
	return total_linh;
}
void backTrack(int stt_door, int cost) {
	//dk dung
	if (cost > min1)   return;
	if (stt_door == n + 1) {
		if (min1 > cost) {
			min1 = cost;
		}
		return;
	}
	for (int i = 0; i < 3; i++) {
		//th pass
		if (i == 0) {
			backTrack(stt_door + 1, cost + door[stt_door].cost);
		}
		//th hire
		if (i == 1) {
			status[0][stt_door] = door[stt_door].num_linh;
			backTrack(stt_door + 1, cost + 2*door[stt_door].cost);
			status[0][stt_door] = 0;
		}
		//th battle
		if (i == 2) {
			int num_linh = totalLinhDeDanh();
			int num_linh_hy_sinh = totalLinhHySinh();
			if (num_linh - num_linh_hy_sinh < door[stt_door].num_linh)  return;
			if (num_linh - num_linh_hy_sinh >= door[stt_door].num_linh) {
				status[0][stt_door] = door[stt_door].num_linh;
				status[1][stt_door] = -1;
				for (int i = 1; i < stt_door; i++) {
					if (status[0][i] != 0 && status[1][i] != -1) {
						status[1][i] += 1;
					}
				}
				backTrack(stt_door + 1, cost);
				for (int i = 1; i < stt_door; i++) {
					if (status[0][i] != 0 && status[1][i] != -1) {
						status[1][i] -= 1;
					}
				}
				status[0][stt_door] = 0;
				status[1][stt_door] = 0;
			}
		}
	}
}
int main() {
	cin >> t;
	for (int tc = 0; tc < t; tc++) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			status[0][i] = status[1][i] = 0;
		}
		for (int i = 1; i <= n; i++) {
			cin >> door[i].num_linh >> door[i].cost;
		}
		min1 = 1000000;
		backTrack(1,0);
		cout << "#" << tc + 1 << " " << min1 << endl;
	}
	return 0;
}
Editor is loading...
Leave a Comment