Untitled
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