题目
#include<bits/stdc++.h>
using namespace std;
int pai[20],T;
//pai[]统计牌的数量
int n;
int ans;
void shunzi(int step);//顺子
void feiji(int step);//飞机
void liandui(int step);//连对
int sanpai();
void chupai(int step){
if (step>=ans)
return;
ans=min(ans,step+sanpai());
feiji(step);
shunzi(step);
liandui(step);
}
void shunzi(int step){
int l=0;
for (int i=3;i<=13;i++){
l=0;
while (pai[i+l]>=1)
l++;
for (int j=l;j>=5;j--){
for (int k=i;k<=i+j-1;k++)
pai[k]=pai[k]-1;
chupai(step+1);
for (int k=i;k<=i+j-1;k++)
pai[k]=pai[k]+1;
}
}
}
void feiji(int step){
int l=0;
for (int i=3;i<=13;i++){
l=0;
while (pai[i+l]>=3)
l++;
for (int j=l;j>=2;j--){
for (int k=i;k<=i+j-1;k++)
pai[k]=pai[k]-3;
chupai(step+1);
for (int k=i;k<=i+j-1;k++)
pai[k]=pai[k]+3;
}
}
}
void liandui(int step){
int l=0;
for (int i=3;i<=13;i++){
l=0;
while (pai[i+l]>=2)
l++;
for (int j=l;j>=3;j--){
for (int k=i;k<=i+j-1;k++)
pai[k]=pai[k]-2;
chupai(step+1);
for (int k=i;k<=i+j-1;k++)
pai[k]=pai[k]+2;
}
}
}
int sanpai(){
bool wangzha=false; // 可不可以王炸
if (pai[1]==2)
wangzha=true;
int zhangshu[5];
memset(zhangshu,0,sizeof(zhangshu));
for (int i=2;i<=14;i++)
zhangshu[pai[i]]++;
zhangshu[1]+=pai[1];
int num=0;
if (zhangshu[2]==0&&zhangshu[3]==0&&zhangshu[4]==0&&wangzha==false)
return zhangshu[1];
if (zhangshu[2]==0&&zhangshu[3]==0&&zhangshu[4]==0&&wangzha)
return zhangshu[1]-1;
//以下1、2、3、4都代表出一种有1或2或3或4张的牌
//炸->3+1 * 4+2 + 3+1 step 2
while (!zhangshu[3]&&zhangshu[4]>=2&&zhangshu[1]==1&&zhangshu[2]==1){
zhangshu[4]--;
zhangshu[4]--;
zhangshu[1]--;
zhangshu[2]--;
num=num+2;
}
//3->2+1 * 4+2 3+1 step 2
while (!zhangshu[2]&&zhangshu[4]==1&&zhangshu[3]>=2&&zhangshu[1]==1){
zhangshu[3]-=2;
zhangshu[4]--;
zhangshu[1]--;
num+=2;
}
//3+4>2+1 3->2+1 * 4+2*2 1
if (zhangshu[3]+zhangshu[4]>zhangshu[2]+zhangshu[1])
while (zhangshu[4]&&zhangshu[3]&&zhangshu[2]){
zhangshu[3]--;
zhangshu[4]--;
zhangshu[2]--;
zhangshu[1]++;
num++;
}
//
if (zhangshu[3]+zhangshu[4]>zhangshu[2]+zhangshu[1])
while (zhangshu[4]>=2&&zhangshu[3]>=2){
zhangshu[3]-=2;
zhangshu[4]-=2;
num+=2;
}
//3+4>2+1 3->2+1 * 4+2*1 2
if (zhangshu[3]+zhangshu[4]>zhangshu[2]+zhangshu[1])
while (zhangshu[4]&&zhangshu[3]&&zhangshu[1]){
zhangshu[1]--;
zhangshu[3]--;
zhangshu[4]--;
zhangshu[2]++;
num++;
}
//4+2*1
while (zhangshu[4]&&zhangshu[1]>1){
zhangshu[4]--;
zhangshu[1]-=2;
num++;
}
//4+2*2
while (zhangshu[4]&&zhangshu[2]>1){
zhangshu[4]--;
zhangshu[2]-=2;
num++;
}
//2->1+1 4+1+1
while (zhangshu[4]&&zhangshu[2]){
zhangshu[4]--;
zhangshu[2]--;
num++;
}
//3->1+2 * 3+1 3+2
if (zhangshu[3]%3==0&&zhangshu[1]+zhangshu[2]<=1)
while (zhangshu[3]>=3){
zhangshu[3]-=3;
num+=2;
}
//3+1
while (zhangshu[3]&&zhangshu[1]){
zhangshu[3]--;
zhangshu[1]--;
num++;
}
//3+2
while (zhangshu[3]&&zhangshu[2]){
zhangshu[3]--;
zhangshu[2]--;
num++;
}
//4->2 + 1*2 3+2 4+1*2
while (zhangshu[4]>1&&zhangshu[3]){
zhangshu[4]-=2;
zhangshu[3]--;
num+=2;
}
//4->2*2 3+2 3+2
while (zhangshu[4]&&zhangshu[3]>1){
zhangshu[4]--;
zhangshu[3]-=2;
num+=2;
}
//3->1+2 * 3+1 3+2
while (zhangshu[3]>2){
zhangshu[3]-=3;
num+=2;
}
//4->2+2 * 4+2*2
while (zhangshu[4]>1){
zhangshu[4]-=2;
num+=1;
}
if (wangzha==true&&zhangshu[1]>=2)
return num+zhangshu[1]+zhangshu[2]+zhangshu[3]+zhangshu[4]-1;
else
return num+zhangshu[1]+zhangshu[2]+zhangshu[3]+zhangshu[4];
}
int main(){
scanf("%d%d",&T,&n);
while (T--){
ans=n;
memset(pai,0,sizeof(pai));
for (int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
if (x==1){
pai[14]++;
}
else if (x==0)
pai[1]++;
else
pai[x]++;
}
chupai(0);//出牌
printf("%d
",ans);
return 0;
}
return 0;
}
//此方法参照luogu题解