题目大意：要将一个大矩形內的所有小矩形涂色，涂色要求，只有该矩形上面的所有矩形都涂色了才可以涂该颜色，换一种填涂的颜色就要花费一点体力值，问填涂完需要花费的最小体力值
解题思路：先处理一下填涂该矩形的前提条件，，我用了一个can数组表示填涂该矩形时要满足的状态量 用dp[color][state]表示当前用的颜色是color，填涂的状态为state时所用的最少体力值 然后暴力得出转换和结果
;Rectangles{int x1, x2, y1, y2, color;}Rec[maxn];struct paiting{int s, color;}start;int n;int can[maxn];int dp[maxc][maxs];bool judge(int i, int j) {if (Rec[j].y2 <= Rec[i].y1)if (((Rec[j].x1 <= Rec[i].x1 && Rec[j].x2 > Rec[i].x1 && Rec[j].x2 <= Rec[i].x2) || (Rec[j].x2 >= Rec[i].x2 && Rec[j].x1 >= Rec[i].x1 && Rec[j].x1 < Rec[i].x2)))return true;return false;}void init() {scanf(“%d”, &n);for (int i = 0; i < n; i++)scanf(“%d%d%d%d%d”, &Rec[i].y1, &Rec[i].x1, &Rec[i].y2, &Rec[i].x2, &Rec[i].color);memset(can, 0, sizeof(can));for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j)continue;if (judge(i, j))can[i] |= (1 << j);}}memset(dp, 0x3f, sizeof(dp));dp[0][0] = 0;}void solve() {queue<paiting> q;start.s = 0;start.color = 0;q.push(start);while (!q.empty()) {paiting t = q.front();q.pop();int state = t.s;int color = t.color;for (int i = 0; i < n; i++)if ((state & (1 << i)) == 0 && (state & can[i]) == can[i]) {if (Rec[i].color == color) {dp[color][state | (1 << i)] = min(dp[color][state | (1 << i)], dp[color][state]);}else {dp[Rec[i].color][state | (1 << i)] = min(dp[Rec[i].color][state | (1 << i)], dp[color][state] + 1);}paiting tt;tt.s = state | (1 << i);tt.color = Rec[i].color;q.push(tt);}}int ans = INF;for (int i = 0; i < maxc; i++)ans = min(ans, dp[i][(1 << n) – 1]);printf(“%d\n”, ans);}int main() {int test;scanf(“%d”, &test);while (test–) {init();solve();}return 0;}
把自己当傻瓜，不懂就问，你会学的更多
