看上去相当复杂的一道题，实际上有一个强剪枝。计算面积！面积相符合的情况下搜索。
为了简便写了一个位操作。当初JTP就是在这道题上战胜了ZJU的……
#include <cstdio>#include <string>int T, W, L, N, bx[10], by[10], a[30][30], ac, area, ba[10];int v[10], p[10];void init ();void dfs ();int in ( int x, int y, int, int );void put ( int x, int y, int, int, int n );void pa ();void proc ();int main ()
...{
//freopen ( "in.txt", "r", stdin ); int i; scanf ( "%d", &T ); for ( i = 0; i < T; i ++ )
...{ init (); proc (); //dfs (); if ( ac ) printf ( "YES " ); else printf ( "NO " );
} return 0;
}void init ()...{ scanf ( "%d%d", &W, &L ); scanf ( "%d", &N ); //memset ( a, 0, sizeof ( a ) ); //memset ( v, 0, sizeof ( v ) ); //memset ( s, 0, sizeof ( s ) ); int i, j, t; for ( i = 0; i < N; i ++ ) ...{ scanf ( "%d%d", &bx[i], &by[i] ); ba[i] = bx[i] * by[i]; if ( bx[i] > by[i] ) ...{ t = bx[i]; bx[i] = by[i]; by[i] = t; } } area = W * L; ac = 0;}void dfs ()...{ //pa (); if ( ac ) return; else ...{ int i, j, ox = -1, oy = -1; for ( i = 0; i < W; i ++ ) ...{ for ( j = 0; j < L; j ++ ) ...{ if ( a[i][j] == 0 ) ox = i, oy = j, i = W, j = L; } } if ( ox == -1 ) ...{ //printf ( "ac " ); ac = 1; return; } for ( i = 0; i < N; i ++ ) ...{ if ( !p[i] || v[i] ) continue; v[i] = 1; if ( in ( ox, oy, bx[i], by[i] ) ) ...{ put ( ox, oy, bx[i], by[i], 1 ); dfs (); if ( ac ) return; put ( ox, oy, bx[i], by[i], 0 ); } if ( bx[i] != by[i] && in ( ox, oy, by[i], bx[i] ) ) ...{ put ( ox, oy, by[i], bx[i], 1 ); dfs (); if ( ac ) return; put ( ox, oy, by[i], bx[i], 0 ); } v[i] = 0; } }}int in ( int x, int y, int dx, int dy )...{ int i, j; if ( x + dx > W ) return 0; if ( y + dy > L ) return 0; for ( i = x; i < x + dx; i ++ ) ...{ for ( j = y; j < y + dy; j ++ ) ...{ if ( a[i][j] ) return 0; } } return 1;}void put ( int x, int y, int dx, int dy, int n )...{ int i, j; for ( i = x; i < dx + x; i ++ ) ...{ for ( j = y; j < dy + y; j ++ ) ...{ a[i][j] = n; } }}void pa ()...{ int i, j; for ( i = 0; i < W; i ++ ) ...{ for ( j = 0; j < L; j ++ ) printf ( "%d ", a[i][j] ); printf ( " " ); } printf ( " " );}void proc ()...{ int i, j, sum; for ( i = 0; i < ( 1 << N ); i ++ ) ...{ sum = 0; for ( j = 0; j < N; j ++ ) ...{ p[j] = !!( i & ( 1 << j ) ); if ( p[j] ) sum += ba[j]; } if ( sum == area ) ...{ memset ( v, 0, sizeof ( v ) ); memset ( a, 0, sizeof ( a ) ); //printf ( "i:%d ", i ); dfs (); if ( ac ) return; } }}