TLE 12求助
查看原帖
TLE 12求助
275860
___A__楼主2024/3/17 11:41
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n,m,num,vis[N][N],all,dp[N*N];
struct rec{
	int x,y;
}a[N];
int cmp(rec x,rec y){
	return x.x*x.y>y.x*y.y;
}
int check(int x1,int x2,int y1,int y2){
	for(int i=x1;i<=x2;i++){
		for(int j=y1;j<=y2;j++){
			if(vis[i][j]){
				return 0;
			}
		}
	}
	return 1;
}
void add(int x1,int x2,int y1,int y2,int val){
	for(int i=x1;i<=x2;i++){
		for(int j=y1;j<=y2;j++){
			vis[i][j]+=val;
		}
	}
}
void dfs(int now){
	if(now>num){
		if(!all){
			cout<<"Yes";
		    exit(0);
		}
		return;
	}
	dfs(now+1);//x[i]*y[i]
	for(int i=1;i<=n-a[now].x+1;i++){
		for(int j=1;j<=m-a[now].y+1;j++){
			if(check(i,i+a[now].x-1,j,j+a[now].y-1)){
				add(i,i+a[now].x-1,j,j+a[now].y-1,1),all-=a[now].x*a[now].y,dfs(now+1),add(i,i+a[now].x-1,j,j+a[now].y-1,-1),all+=a[now].x*a[now].y;
			}
		}
	}
	if(a[now].x!=a[now].y){
	    swap(a[now].x,a[now].y);
	    for(int i=1;i<=n-a[now].x+1;i++){
		    for(int j=1;j<=m-a[now].y+1;j++){
			    if(check(i,i+a[now].x-1,j,j+a[now].y-1)){
				    add(i,i+a[now].x-1,j,j+a[now].y-1,1),all-=a[now].x*a[now].y,dfs(now+1),add(i,i+a[now].x-1,j,j+a[now].y-1,-1),all+=a[now].x*a[now].y;
			    }
		    }
		}
	}
}
int main(){
	cin>>num>>n>>m,all=n*m,dp[0]=1;
	for(int i=1;i<=num;i++){
		cin>>a[i].x>>a[i].y;
		for(int j=N*N-1;j>=a[i].x*a[i].y;j--){
			dp[j]|=dp[j-a[i].x*a[i].y];
		}
	}
	sort(a+1,a+num+1,cmp);
	if(!dp[n*m]){
		cout<<"No";
		return 0;
	}
	dfs(1),cout<<"No";
}
2024/3/17 11:41
加载中...