题意：N(1 <= N <= 15)个矩形，每个矩形要涂上指定的颜色C(1 <= C <= 20)，如果给一个矩形涂色，那么与它相邻的上方矩形必须已经涂色，问最少要取几次画笔。
题目链接：http://poj.org/problem?id=1691
——>>状态：dp[S][color] 表示达到状态 S 且最后一次涂色为 color 时的最小取画笔数
状态转移方程：dp[S][color] = min(dp[S][color], dp[sub][i]); 或者 dp[S][color] = min(dp[S][color], dp[sub][i] + 1);
时间复杂度：O(N * C * 2 ^ N)
#include <cstdio>
#include <algorithm>
#include <cstring>using std::min;const int MAX_COLOR = 20;
const int MAX_RECTANGLE = 15;
const int INF = 0x3f3f3f3f;struct RECTANGLE
{int ly;int lx;int ry;int rx;int color;int fa[MAX_RECTANGLE];int cnt;
} r[MAX_RECTANGLE];int M, N;
int dp[1 << MAX_RECTANGLE][MAX_COLOR + 1];void Read()
{scanf("%d", &N);for (int i = 0; i < N; ++i){scanf("%d%d%d%d%d", &r[i].ly, &r[i].lx, &r[i].ry, &r[i].rx, &r[i].color);r[i].cnt = 0;}
}void Init()
{for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){if (j != i && r[j].ry == r[i].ly && r[j].rx > r[i].lx && r[j].lx < r[i].rx){r[i].fa[r[i].cnt++] = (1 << j);}}}
}bool IsReady(int x, int S)
{for (int i = 0; i < r[x].cnt; ++i){if (!(r[x].fa[i] & S)){return false;}}return true;
}int Idx(int x)
{int i = 0;while ((1 << i) != x){++i;}return i;
}void Dp()
{memset(dp, 0x3f, sizeof(dp));for (int i = 1; i <= MAX_COLOR; ++i){dp[0][i] = 1;}for (int S = 1; S <= (1 << N) - 1; ++S){for (int t = S; t; t -= t & -t){int cur = Idx(t & -t);int sub = S & ~(t & -t);int color = r[cur].color;if (IsReady(cur, sub)){for (int i = 1; i <= MAX_COLOR; ++i){if (color == i){dp[S][color] = min(dp[S][color], dp[sub][i]);}else{dp[S][color] = min(dp[S][color], dp[sub][i] + 1);}}}}}
}void Output()
{int ret = INF;for (int i = 1; i <= 20; ++i){ret = min(ret, dp[(1 << N) - 1][i]);}printf("%d\n", ret);
}int main()
{scanf("%d", &M);while (M--){Read();Init();Dp();Output();}return 0;
}