悬记,66照着题解第二篇抄的暴力,但是没抄对,球跳
查看原帖
悬记,66照着题解第二篇抄的暴力,但是没抄对,球跳
658008
a1a2a3a4a5楼主2023/8/18 19:21

求求各位大佬看一下我写的代码,我觉得天衣无缝,但是就是过不了好几个点,我非常的生气,求求大佬帮我挑挑代码,如果谁可以帮我调出代码,我会记住他一辈子。

#include<bits/stdc++.h>
using namespace std;
int T,n,o1,da,p[21];
void dfs(int x,int c,int s,int pai[])
{
	if(c>=da) return ;
	if(s==0) {da=c;return ;}
	if(x==16) return ;
	if(pai[x]==0) dfs(x+1,c,s,pai);
	if(pai[15]&&pai[16]) pai[15]--,pai[16]--,dfs(x,c+1,s-2,pai),pai[15]++,pai[16]++;
	if(pai[x]>=4)
	{
		pai[x]-=4,dfs(x,c+1,s-4,pai);
		for(int i=1;i<=16;i++)
			if(pai[i]>=1)
			{
				pai[i]--;
				for(int j=i;j<=16;j++)
					if(pai[j]>=1)
						pai[j]--,dfs(x,c+1,s-6,pai),pai[j]++;
				pai[i]++;
			}
		for(int i=1;i<=16;i++)
			if(pai[i]>=2)
			{
				pai[i]-=2;
				for(int j=i;j<=16;j++)
					if(pai[j]>=2)
						pai[j]-=2,dfs(x,c+1,s-8,pai),pai[j]+=2;
				pai[i]+=2;
			}
		pai[x]+=4;
	}
	if(pai[x]>=3)
	{
		pai[x]-=3;
		dfs(x,c+1,s-3,pai);
		for(int i=1;i<=16;i++)
			if(pai[i]>=1) pai[i]--,dfs(x,c+1,s-4,pai),pai[i]++;
		for(int i=1;i<=16;i++)
			if(pai[i]>=2) pai[i]-=2,dfs(x,c+1,s-5,pai),pai[i]+=2;
		for(int i=x+1;i<=16;i++)
		{
			if(pai[i]<3) {for(int j=x+1;j<i;j++) pai[j]+=3;break;}
			pai[i]-=3;
			if(i-x+1>=2) dfs(x,c+1,s-(i-x+1)*3,pai);
		}
		pai[x]+=3;
	}
	if(pai[x]>=2)
	{
		pai[x]-=2,dfs(x,c+1,s-2,pai);
		for(int i=1;i<=16;i++)
			 if(i==x) continue;
			 else 
			if(pai[i]>=3) pai[i]-=3,dfs(x,c+1,s-5,pai),pai[i]+=3;
		for(int i=x+1;i<=16;i++)
		{
			if(pai[i]<2) {for(int j=x+1;j<i;j++) pai[j]+=2;break;}
			pai[i]-=2;
			if(i-x+1>=3) dfs(x,c+1,s-(i-x+1)*2,pai);
		}
		for(int i=1;i<=16;i++)
			if(i==x) continue;
			else if(pai[i]>=4)
			{
				pai[i]-=4;
				for(int j=i+1;j<=16;j++)
					if(pai[j]>=2)
						pai[j]-=2,dfs(x,c+1,s-8,pai),pai[j]+=2;
				pai[i]+=4;
			}
		pai[x]+=2;
	}
	if(pai[x]>=1)
	{
		pai[x]--,dfs(x,c+1,s-1,pai);
		for(int i=1;i<=16;i++)
			 if(i==x) continue;
			 else 
			if(pai[i]>=3) pai[i]-=3,dfs(x,c+1,s-4,pai),pai[i]+=3;
		for(int i=x+1;i<=16;i++)
		{
			if(pai[i]<1) {for(int j=x+1;j<i;j++) pai[j]+=1;break;}
			pai[i]-=1;
			if(i-x+1>=5) dfs(x,c+1,s-i+x-1,pai);
		}
		for(int i=1;i<=16;i++)
			if(i==x) continue;
			else if(pai[i]>=4)
			{
				pai[i]-=4;
				for(int j=i+1;j<=16;j++)
					 if(j!=i) continue;
					 else if(pai[j]>=1)
							pai[j]--,dfs(x,c+1,s-6,pai),pai[j]++;
				pai[i]+=4;
			}
		pai[x]++;
	}
}
int main()
{
	cin>>T>>n;
	for(int i1=1;i1<=T;i1++)
	{
		memset(p,0,sizeof(p)),da=0x3f3f3f3f;
		for(int i=1,a,b;i<=n;i++)
		{
			cin>>a>>b;
			if(a==1) p[12]++; 
			else if(a==2) p[14]++;
			else if(a!=0) p[a-2]++;
			else if(b==1) p[15]++;
			else p[16]++;
		}
		dfs(1,0,n,p);
		cout<<da<<"\n";
	}
	return 0;
}
/*
1 8 7 4 8 4 9 1 10 4 11 1 5 1 1 4 1 1
1 17 12 3 4 3 2 3 5 4 10 2 3 3 12 2 0 1 1 3 10 1 6 2 12 1 11 3 5 2 12 4 2 2 7 2
*/
2023/8/18 19:21
加载中...