大致题意就是一些火柴棍拼成了许多正方形，问最少拿掉几根可以把所有正方形都破坏掉。其实背后的模型就是说给你若干个子集，要求取最少个数的子集，使它们能覆盖整个全集。同样模型的题目还有UVA 10160。
首先要初始化一下，把重叠的或者有包含关系的子集都去掉，比如A = B或者A包含于B，则A就可以去掉不要考虑了。然后然后用DFS加剪枝就可以过。基本的DFS我就不说了。当DFS到某一个节点时，如果发生以下情况之一，则该节点就不要再往下发展了，也就是所谓的剪枝：
1. 当前已取的子集数量超过了先前已搜到的最优解，则再发展下去也不可能搜出更优的解了。这个最优解的初始值是所有子集的总数（所有子集都取了总归能覆盖全集了吧）。
2. 在当前一步的基础上取了某个子集后，覆盖的集合没有发生变改，则新取的这个子集是没有义意的，所以就不要在它身上发展下一层节点了。
3. 在当前已经覆盖的集合的基础上，即使把之后所有的子集都加上也无法覆盖整个全集的话，那也没有必要搜下去了。
有了这几个剪枝，在时间数量级上就足够快了。但是要真正的速度够快的话还需要一些常数级的优化，比如：
1. 用位操作表示集合的交、并、补。
2. 上面说的第3个剪枝当中，"之后所有的子集所能覆盖的集合"可以在一开使就计算好，以避免重复计算。
另外，还有一个优化，就是一开始把所有子集按基数（元素的个数）从大到小排序。搜的每一步总是先取基数最大的一个子集。这样比较有可能较早地找到最优解，当然只是可能而已。
有了这些优化就差不多了。虽然极限数据过不了，但是这道题本身的测试数据很弱，我只用了0.031秒。
PS. 2008-SEP-03. 应某网友要求，贴一下代码，如下：（现在看自己以前的代码，风格都有点不认识了。
）#include <iostream>
#include <cstring>
using namespace std;
const int MAX_SIZE = 5;
const int MAX_STK = 60;
typedef unsigned long long ULL;
class CoverInit {
private:
static int m_size;
//Number of the stick on the top of the grid [row][col].
static int m_up[MAX_SIZE][MAX_SIZE];
static void initUp() {
for (int i = 0; i < m_size; i++) {
m_up[i][0] = i * (2 * m_size + 1);
for (int j = 1; j < m_size; j++) {
m_up[i][j] = m_up[i][j - 1] + 1;
}
}
}
static void initSqr(int firstStick, int size, ULL mask, ULL* cover) {
int gap = 2 * m_size + 1;
int num = firstStick;//The upper and the lower edges.
for (int i = 0; i < size; i++) {
cover[num] |= mask;
cover[num + size * gap] |= mask;
num++;
}
num = firstStick + m_size;//The left and the right edges.
for (int i = 0; i < size; i++) {
cover[num] |= mask;
cover[num + size] |= mask;
num += gap;
}
}
public:
static void initCover(int size, ULL* cover, int stkCnt) {
m_size = size;
initUp();
memset(cover, 0, stkCnt * sizeof(ULL));
ULL mask = 1ULL;
for (int sqrSize = 1; sqrSize <= m_size; sqrSize++) {
for (int i = 0; i <= m_size - sqrSize; i++) {
for (int j = 0; j <= m_size - sqrSize; j++) {
int up = m_up[i][j];
initSqr(up, sqrSize, mask, cover);
mask <<= 1;
}
}
}
}
};
int CoverInit::m_size;
int CoverInit::m_up[MAX_SIZE][MAX_SIZE];
class Solution {
private:
ULL m_cover[MAX_STK];
bool m_stick[MAX_STK];
ULL m_universal;
int m_sqrCnt;
int m_stkCnt;
int m_minStk;
ULL m_remainCov[MAX_STK];
void dfs(char stkCnt, char lastStk, ULL cover) {
if (cover == m_universal) {
m_minStk = stkCnt;
}
else {
if (stkCnt < m_minStk
&& (m_remainCov[lastStk + 1] | cover) == m_universal
) {
for (int i = lastStk + 1; i < m_stkCnt; i++) {
if ((m_cover[i] | cover) > cover) {
dfs(stkCnt + 1, i, cover | m_cover[i]);
}
}
}
}
}
void init(int size) {
m_stkCnt = 2 * size * (size + 1);
CoverInit::initCover(size, m_cover, m_stkCnt);
int sqrCnt = 0;
for (int i = 1; i <= size; i++) {
sqrCnt += i * i;
}
m_universal = 1ULL;
for (int i = 1; i < sqrCnt; i++) {
m_universal <<= 1;
m_universal += 1ULL;
}
for (int i = 0 ; i < m_stkCnt; i++) {
m_stick[i] = true;
}
}
void modifyData() {
for (int i = 0; i < m_stkCnt; i++) {
if (!m_stick[i]) {
m_universal &= ~m_cover[i];
}
}
for (int i = 0; i < m_stkCnt; i++) {
m_cover[i] &= m_universal;
}
for (int i = 0; i < m_stkCnt; i++) {
if (m_stick[i]) {
for (int j = 0; j < m_stkCnt; j++) {
if (j != i && m_stick[j]
&& m_cover[j] == (m_cover[j] & m_cover[i])
) {
m_stick[j] = false;
}
}
}
}
int cnt = 0;
for (int i = 0; i < m_stkCnt; i++) {
if (m_stick[i]) {
m_cover[cnt] = m_cover[i];
cnt++;
}
}
m_stkCnt = cnt;
m_remainCov[m_stkCnt - 1] = m_cover[m_stkCnt - 1];
for (int i = m_stkCnt - 2; i >= 0; i--) {
m_remainCov[i] = m_remainCov[i + 1] | m_cover[i];
}
}
public:
void input() {
int size;
cin >> size;
init(size);
int rmCnt;
cin >> rmCnt;
for (int i = 0; i < rmCnt; i++) {
int rm;
cin >> rm;
m_stick[rm - 1] = false;
}
}
void search() {
modifyData();
m_minStk = m_stkCnt < 9? m_stkCnt: 9;
dfs(0, -1, 0ULL);
cout << m_minStk << endl;
}
};
int main() {
Solution solution;
int caseCnt;
cin >> caseCnt;
for (int i = 0; i < caseCnt; i++) {
solution.input();
solution.search();
}
return 0;
}
