我不會長大後再學習我不會長大後再學習我不會長大後再學習我不會長大後再學習我不會長大後再學習我不會長大後再學習 ...
本文同步發表於洛谷。
是個逆天搜索。
最開始：爆搜，啟動！
然後 TLE 到飛起。
賽後：我【數據刪除】這麼簡單的嗎？！
dfs 每個位置，試著把沒放過的塊放到以這個位置為左上角的區域裡面。
好了沒了，就是這麼簡單！
對了記得這個塊可以旋轉！
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
i128 f=1;
x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
void writing(i128 x)
{
if(x>=10)writing(x/10);
putchar(x%10+'0');
}
void write(i128 x)
{
if(x<0)
{
cout<<'-';
x=-x;
}
writing(x);
}
LL n,h,w,a[20],b[20];
bool vis[20][20],u[20];
void dfs(LL x,LL y)
{
if(y>w)dfs(x+1,1);
if(x>h)
{
cout<<"Yes"<<endl;
exit(0);
}
if(vis[x][y])dfs(x,y+1);
rep(i,1,2*n,1)
{
if(!u[(i-1)%n+1])
{
bool f=1;
repn(xx,x,x+a[i],1)
{
repn(yy,y,y+b[i],1)
{
if(xx>h||yy>w||vis[xx][yy])f=0;
}
}
if(!f)continue;
u[(i-1)%n+1]=1;
repn(xx,x,x+a[i],1)
{
repn(yy,y,y+b[i],1)
{
vis[xx][yy]=1;
}
}
dfs(x,y+1);
u[(i-1)%n+1]=0;
repn(xx,x,x+a[i],1)
{
repn(yy,y,y+b[i],1)
{
vis[xx][yy]=0;
}
}
}
}
}
int main()
{
cin>>n>>h>>w;
rep(i,1,n,1)cin>>a[i]>>b[i];
rep(i,n+1,2*n,1)
{
a[i]=b[i-n];
b[i]=a[i-n];
}
dfs(1,1);
cout<<"No"<<endl;
return 0;
}
