好哥哥们 好姐姐们 WA了两个 求调 <^~^>
查看原帖
好哥哥们 好姐姐们 WA了两个 求调 <^~^>
739226
yxans楼主2024/3/19 21:01

rt <^~^>

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int zyc = 15 ;//<^~^>

int h,w,n,v[zyc],vis[zyc][zyc],top,u[zyc],pop;
bool flag = 0;

struct Zyc{
	int x,y;
}t[zyc];

inline bool cmp(Zyc a,Zyc b){
	return (a.x*a.y>b.x*b.y);
}

inline int read(){
	int x;
	scanf("%lld",&x);
	return x;
}

inline void dfs(int u){
	if(u==pop+1){
		flag=1;
		return ;
	}
	if(flag)  return; 
	int now=v[u];
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			bool yc = 0;
			for(int k=i;k<=i+t[now].x-1;k++){
				for(int l=j;l<=j+t[now].y-1;l++){
					if(vis[k][l]||k>h||l>w){
						yc=1;
						break;	
					}
				}
				if(yc)  break;
			} 
			if(yc)  continue;
			for(int k=i;k<=i+t[now].x-1;k++)
				for(int l=j;l<=j+t[now].y-1;l++)
					vis[k][l]=1;
			dfs(u+1);
			for(int k=i;k<=i+t[now].x-1;k++)
				for(int l=j;l<=j+t[now].y-1;l++)
					vis[k][l]=0;
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			bool yc = 0;
			for(int k=i;k<=i+t[now].y-1;k++){
				for(int l=j;l<=j+t[now].x-1;l++){
					if(vis[k][l]||k>h||l>w){
						yc=1;
						break;	
					}
				}
				if(yc)  break;
			} 
			if(yc)  continue;
			for(int k=i;k<=i+t[now].y-1;k++)
				for(int l=j;l<=j+t[now].x-1;l++)
					vis[k][l]=1;
			dfs(u+1);
			for(int k=i;k<=i+t[now].y-1;k++)
				for(int l=j;l<=j+t[now].x-1;l++)
					vis[k][l]=0;
		}
	}
}
signed main(){
	n=read();h=read();w=read();
	for(int i=1;i<=n;i++)
		t[i].x=read(),t[i].y=read();
	sort(t+1,t+n+1,cmp);//剪枝<^~^> 
	for(int i=0;i<(1<<n);i++){//选择面积合适的砖 
		int yc=i,sum=0,cnt=0;
		while(yc){
			++cnt;
			if(yc&1)  sum+=t[cnt].x*t[cnt].y;
			yc>>=1;
		}
		if(sum==h*w){
			u[++top]=i;
		}
	}
	for(int i=1;i<=top&&!flag;i++){
		int yc=u[i],cnt=0;
		pop=0;
		while(yc){
			++cnt;
			if(yc&1)  v[++pop]=cnt;
			yc>>=1;
		} 
		dfs(1);
//		memset(vis,0,sizeof(vis));
		for(int j=1;j<=zyc-1;j++)
			for(int k=1;k<=zyc-1;k++)
				vis[j][k]=0;
	}
	if(flag)  return 0*printf("Yes\n");
	return 0*printf("No\n");
}

2024/3/19 21:01
加载中...