Untitled
plain_text
a month ago
1.3 kB
4
Indexable
Never
#include <iostream> #include <stdio.h> using namespace std; int T, n; int a[200][2], dam[200][2]; int kq = 0; void dequy(int gg, int count = 0) { if(gg == n) { if(kq > count) kq = count; return; } if(count > kq) return; //pass dequy(gg+1, count + a[gg][1]); //buy dam[gg][0] = a[gg][0]; dequy(gg+1, count + 2*a[gg][1]); dam[gg][0] = 0; //attack int linh = 0; int thua = a[gg][0]; for(int i = 0; i < n; i++) { if(dam[i][1] < 3) linh += dam[i][0]; } if(linh >= thua) { int sav[200][2]; for(int i = 0; i < n; i++) { sav[i][0] = dam[i][0]; sav[i][1] = dam[i][1]; } for(int i = 0; i < n; i++) { if(dam[i][1] < 3 && dam[i][0] > 0) { if(dam[i][0] - thua <= 0) { thua -= dam[i][0]; dam[i][0] = 0; dam[i][1] ++; } else { dam[i][0] = dam[i][0] - thua; thua = 0; dam[i][1] ++; } } } dequy(gg+1, count); for(int i = 0; i < n; i++) { dam[i][0] = sav[i][0]; dam[i][1] = sav[i][1]; } } } int main() { freopen("input.txt", "r", stdin); cin >> T; for (int stt = 1; stt <= T; stt++) { cin >> n; for(int i = 0; i < n; i ++) { cin >> a[i][0] >> a[i][1]; dam[i][0] = 0; dam[i][1] = 0; } kq = 100000; dequy(0); cout << "#" << stt << " " << kq << endl; } return 0; }