只差两个点,不想大改代码了,求助
#include<bits/stdc++.h>
using namespace std;
#define int long long
int c[20], t, n, x, y, s, d, ans;
#include<cctype>
inline int read() {
int X = 0, w = 0;
char ch = 0;
while (!isdigit(ch)) {
w |= ch == '-';
ch = getchar();
}
while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
return w ? -X : X;
}
void dfs(int step, int num) {
if (step >= ans) return ;
if (num == 0) {
ans = min(ans, step);
return ;
}
// for(int i=2;i<=15;i++) cout<<c[i]<<" ";
// cout<<"\n"<<step<<" "<<num<<"\n\n";
int s1 = 0, s2 = 0, s3 = 0;
for (int i = 3; i <= 14; i++) {
s1++;
s2++;
s3++;
if (!c[i]) s1 = 0;
if (c[i] < 2) s2 = 0;
if (step + 1 >= ans) return ;
if (c[i] < 3) s3 = 0;
// cout<<s1<<" "<<s2<<" "<<s3<<" 114514\n";
if (s3 >= 2) {
for (int j = i; j >= i - s3 + 1; j--) c[j] -= 3;
dfs(step + 1, num - s3 * 3);
for (int j = i; j >= i - s3 + 1; j--) c[j] += 3;
}
if (step + 1 >= ans) return ;
if (s2 >= 3) {
for (int j = i; j >= i - s2 + 1; j--) c[j] -= 2;
dfs(step + 1, num - s2 * 2);
for (int j = i; j >= i - s2 + 1; j--) c[j] += 2;
}
if (step + 1 >= ans) return ;
if (s1 >= 5) {
for (int j = i; j >= i - s1 + 1; j--) c[j]--;
dfs(step + 1, num - s1);
for (int j = i; j >= i - s1 + 1; j--) c[j]++;
}
if (step + 1 >= ans) return ;
}
// cout<<"1\n";
for (int i = 2; i <= 14; i++) {
if (c[i] == 4) {
c[i] -= 4;
for (int j = 2; j <= 14; j++) { //四带二对
if (c[j] >= 2) {
c[j] -= 2;
for (int k = 2; k <= 14; k++) {
if (c[k] >= 2) {
c[k] -= 2;
dfs(step + 1, num - 8);
c[k] += 2;
}
}
c[j] += 2;
}
}
if (step + 1 >= ans) return ;
for (int j = 2; j <= 15; j++) {//四带二
if (c[j]) {
c[j] --;
for (int k = 2; k <= 15; k++) {
if (c[k]) {
c[k] --;
dfs(step + 1, num - 6);
c[k] ++;
}
}
c[j] ++;
}
if (step + 1 >= ans) return ;
}
c[i] += 4;
}
}
if (step + 1 >= ans) return ;
// cout<<"2\n";
for (int i = 2; i <= 14; i++) {
if (c[i] >= 3) {
c[i] -= 3;
for (int j = 2; j <= 14; j++) { //三带一对
if (c[j] >= 2) {
c[j] -= 2;
dfs(step + 1, num - 5);
c[j] += 2;
}
}
if (step + 1 >= ans) return ;
for (int j = 2; j <= 15; j++) { //三带一
if (c[j]) {
c[j] --;
dfs(step + 1, num - 4);
c[j] ++;
}
}
if (step + 1 >= ans) return ;
c[i] += 3;
}
}
if (step + 1 >= ans) return ;
// cout<<"3\n";
for (int i = 2; i <= 15; i++) {
if (c[i]) step++;
}
dfs(step, 0);
return ;
}
signed main() {
cin >> t >> n;
while (t--) {
ans = 0x3f3f3f3f3f;
for (int i = 1; i <= n; i++) {
x = read();
y = read();
if (x == 1) c[14]++;
else if (x == 0) c[15]++;
else c[x]++;
}
// for(int i=2;i<=15;i++) cout<<c[i]<<" ";
// cout<<"\n";
dfs(0, n);
cout << ans << "\n";
for(int i=2;i<=15;i++) c[i]=0;
}
return 0;
}