Lvat_s Blog

啊

去年NOIP惨不忍睹的回忆

不讲了，暴力dfs就行

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=15;

int test,n,a[N],ans;

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

void dfsa(int x,int y){
if(x==0){ans=min(ans,y);return;}
for(int i=1;i<=14;i++)if(a[i]>0)y+=a[i];
ans=min(ans,y);return;
}

void dfsb(int x,int y){
if(x==0){ans=min(ans,y);return;}
if(a[14]>=2){
	a[14]-=2;
	dfsb(x-2,y+1);
	a[14]+=2;
}
dfsa(x,y);
}

void dfsc(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=13;i++){
	if(a[i]>=2){
		a[i]-=2;
		dfsc(x-2,y+1,i);
		a[i]+=2;
	}
}
dfsb(x,y);
}

void dfsd(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=3){
		a[i]-=3;
		dfsd(x-3,y+1,i);
		a[i]+=3;
	}
}
dfsc(x,y);
}

void dfse(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=4){
		a[i]-=4;
		dfse(x-4,y+1,i);
		a[i]+=4;
	}
}
dfsd(x,y);
}

void dfsf(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=3){
		for(int j=1;j<=14;j++){
			if(j==i)continue;
			else if(a[j]>=1){
				a[i]-=3;
				a[j]--;
				dfsf(x-4,y+1,i);
				a[i]+=3;
				a[j]++;
			}
		}
	}
}
dfse(x,y);
}

void dfsg(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=3){
		for(int j=1;j<=13;j++){
			if(j==i)continue;
			else if(a[j]>=2){
				a[i]-=3;
				a[j]-=2;
				dfsg(x-5,y+1,i);
				a[i]+=3;
				a[j]+=2;
			}
		}
	}
}
dfsf(x,y);
}

void dfsh(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=8;i++){
    for(int j=1;i+j<=13;j++){
        if(a[i+j-1]==0)break;
        if(j>=5){
            for(int k=1;k<=j;k++)a[i+k-1]--;
            dfsh(x-j,y+1,i);
            for(int k=1;k<=j;k++)a[i+k-1]++;
        }
    }
}
dfsg(x,y);
}

void dfsi(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=10;i++){
    for(int j=1;i+j<=13;j++){
        if(a[i+j-1]<2)break;
        if(j>=3){
            for(int k=1;k<=j;k++)a[i+k-1]-=2;
            dfsi(x-j*2,y+1,i);
            for(int k=1;k<=j;k++)a[i+k-1]+=2;
        }
    }
}
dfsh(x,y);
}

void dfsj(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=11;i++){
    for(int j=1;i+j<=13;j++){
        if(a[i+j-1]<3)break;
        if(j>=2){
            for(int k=1;k<=j;k++)a[i+k-1]-=3;
            dfsj(x-j*3,y+1,i);
            for(int k=1;k<=j;k++)a[i+k-1]+=3;
        }
    }
}
dfsi(x,y);
}

void dfsk(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=4){
        for(int j=1;j<=14;j++){
			if(i==j || a[j]==0)continue;
			for(int k=1;k<=14;k++){
				if(i==k || j==k || a[k]==0)continue;
				a[i]-=4;
				a[j]--;
				a[k]--;
				dfsk(x-6,y+1,i);
				a[i]+=4;
				a[j]++;
				a[k]++;
			}
        }
        for(int j=1;j<=14;j++){
			if(i==j)continue;
			if(a[j]<2)continue;
            a[i]-=4;
            a[j]-=2;
            dfsk(x-6,y+1,i);
            a[i]+=4;
            a[j]+=2;
        }
	}
}
dfsj(x,y);
}

void dfsl(int x,int y,int t=1){
if(x==0){ans=min(ans,y);return;}
for(int i=t;i<=14;i++){
	if(a[i]>=4){
        for(int j=1;j<=13;j++){
			if(i==j || a[j]<2)continue;
			for(int k=1;k<=13;k++){
				if(i==k || j==k || a[k]<2)continue;
				a[i]-=4;
				a[j]-=2;
				a[k]-=2;
				dfsl(x-8,y+1,i);
				a[i]+=4;
				a[j]+=2;
				a[k]+=2;
			}
        }
        for(int j=1;j<=13;j++){
			if(i==j && a[j]<8)continue;
            if(a[j]<4)continue;
            a[i]-=4;
            a[j]-=4;
            dfsl(x-8,y+1,i);
			a[i]+=4;
			a[j]+=4;
        }
	}
}
dfsk(x,y);
}

int main(){
freopen("4325.in","r",stdin);
freopen("4325.out","w",stdout);
Read(test);Read(n);
while(test--){
	memset(a,0,sizeof(a));
    for(register int i=1;i<=n;i++){
		int x,y;
		Read(x);Read(y);
		if(x==0)a[14]++;
		else if(x>2)a[x-2]++;
		else a[x+11]++;
    }
	ans=n;
	dfsl(1,0);
	printf("%d\n",ans);
}
return 0;
}