47 lines
1.0 KiB
C++
47 lines
1.0 KiB
C++
#include <stdio.h>
|
|
|
|
int time[10][2];
|
|
int vis[10];
|
|
int T;
|
|
int n;
|
|
|
|
int dfs(int layer, int a_done, int b_done) {
|
|
if (layer > n) {
|
|
return b_done;
|
|
}
|
|
int min = 10000000;
|
|
int me_a_done, me_b_done;
|
|
for (int i = 0; i < n; i++) {
|
|
if (vis[i]) {
|
|
continue;
|
|
}
|
|
|
|
vis[i] = true;
|
|
me_a_done = a_done + time[i][0];
|
|
if (me_a_done > b_done) {
|
|
me_b_done = me_a_done + time[i][1];
|
|
} else {
|
|
me_b_done = b_done + time[i][1];
|
|
}
|
|
int further_min = dfs(layer + 1, me_a_done, me_b_done);
|
|
min = min < further_min ? min : further_min;
|
|
vis[i] = false;
|
|
}
|
|
return min;
|
|
}
|
|
|
|
int main() {
|
|
scanf("%d", &T);
|
|
for (int _ = 0; _ < T; _++) {
|
|
scanf("%d", &n);
|
|
int a, b;
|
|
for (int i = 0; i < n; i++) {
|
|
scanf("%d %d", &a, &b);
|
|
time[i][0] = a;
|
|
time[i][1] = b;
|
|
vis[i] = false;
|
|
}
|
|
printf("%d\n", dfs(1, 0, 0));
|
|
}
|
|
return 0;
|
|
} |