题目描述
blablabla
样例
blablabla
算法
(dfs)
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
const int N = 50;
int a[N], n, res;
void dfs(int x) {
int t = 0;
for (int i = 3; i <= 14; i++) {
if (a[i] < 1)
t = 0;
else {
t++;
if (t >= 5) {
for (int j = i; j >= i - t + 1; j--)
a[j] --;
dfs(x + 1);
for (int j = i; j >= i - t + 1; j--)
a[j] ++;
}
}
}
t = 0;
for (int i = 3; i <= 14; i++) {
if (a[i] < 2)
t = 0;
else {
t++;
if (t >= 3) {
for (int j = i; j >= i - t + 1; j--)
a[j] -= 2;
dfs(x + 1);
for (int j = i; j >= i - t + 1; j--)
a[j] += 2;
}
}
}
t = 0;
for (int i = 3; i <= 14; i++) {
if (a[i] < 3)
t = 0;
else {
t++;
if (t >= 3) {
for (int j = i; j >= i - t + 1; j--)
a[j] -= 3;
dfs(x + 1);
for (int j = i; j >= i - t + 1; j--)
a[j] += 3;
}
}
}
t = 0;
for (int i = 2; i <= 14; i++) {
if (a[i] >= 3) {
a[i] -= 3;
for (int j = 0; j < 15; j++) {
if (j != i) {
if (a[j] >= 1) {
a[j] --;
dfs(x + 1);
a[j] ++;
}
if (a[j] >= 2) {
a[j] -= 2;
dfs(x + 1);
a[j] += 2;
}
}
}
a[i] += 3;
}
if (a[i] >= 4) {
a[i] -= 4;
for (int j = 0; j < 15; j++) {
if (j != i) {
for (int k = 0; k < 15; k++) {
if (k != i && k != j) {
if (a[j] >= 1 && a[k] >= 1) {
a[j] --, a[k]--;
dfs(x + 1);
a[j] ++, a[k]++;
}
if (a[j] >= 2 && a[k] >= 2) {
a[j] -= 2, a[k] -= 2;
dfs(x + 1);
a[j] += 2, a[k] += 2;
}
}
}
}
}
a[i] += 4;
}
}
for (int i = 0; i < 15; i++)
if (a[i])
x++;
res = min(res, x);
}
int main() {
int T;
cin >> T >> n;
while (T--) {
res = INT_MAX;
memset(a, 0, sizeof a);
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d %d", &x, &y);
if (x == 1)
a[14]++;
else if (x == 0)
a[y - 1] ++;
else
a[x] ++;
}
int t = min(a[0], a[1]);
a[0] -= t, a[1] -= t;
dfs(t);
printf("%d\n", res);
}
return 0;
}