POJ 1691 Painting A Board(状態圧縮DP+記憶化探索)

タイトル:
矩形枠はn個の小さな矩形からなり、各矩形に色cを塗布する(以下の図に示すように同じでも異なってもよい).塗布の品質を保証するために、各小マトリクスを塗布するには、その上に位置し、接続された小さな矩形が先に塗布されなければならない条件がある.もちろん条件を満たす同じ色を一緒に塗ることができますが、少なくともブラシ(ブラシ1本につき1色)をどれだけ必要かを聞いてみましょう.
黒書146:平板塗装
考え方:
1.矩形の数は15を超えないので、自然に状態圧縮を利用して問題を解決することを連想し、無後効性を解決するためには1次元を増やさなければならない.dp[i][s]はiで終わる状態sの最小を表す.
2.まず前処理して、矩形iの上の矩形番号、下の解題のためにとても良い敷き詰めをします;
3.残りの仕事は列挙することである:i前にブラシした矩形は、考え方が簡単であまり述べられない.循環に注意する時sは前に置いて、このようにしてやっと求めた結果が互いに影響しないことを保証することができます;
 

#include <iostream>

#include <algorithm>

using namespace std;



const int INFS = 0x3FFFFFFF;



struct POINT {

    int x1, y1, x2, y2;

    int color;

} rect[20] ;



int up[20], dp[15][1<<15];



bool judge(int i, int j) {

    // whether j is upper to i

    if (rect[j].x2 != rect[i].x1) return false;

    if (rect[j].y2 <= rect[i].y1) return false;

    if (rect[j].y1 >= rect[i].y2) return false;

    return true;

}



int workout(int n) {

    for (int i = 0; i < n; i++) {

        up[i] = 0;

        for (int j = 0; j < n; j++)

            if (judge(i, j)) up[i] |= (1<<j);

    }



    int ENDS = (1<<n) - 1;



    for (int i = 0; i < n; i++)

        for (int s = 0; s <= ENDS; s++)

            dp[i][s] = INFS;

    for (int i = 0; i < n; i++)

        if (up[i] == 0) dp[i][1<<i] = 1;



    for (int s = 0; s <= ENDS; s++) {

        for (int i = 0; i < n; i++) {

            if (s & (1<<i)) continue;

            if ((s & up[i]) != up[i]) continue;

            for (int j = 0; j < n; j++) {

                if (!(s & (1<<j))) continue;

                int now = s | (1<<i);

                int value = dp[j][s];

                if (rect[i].color != rect[j].color) value += 1;

                dp[i][now] = min(dp[i][now], value);

            }

        }

    }

    int ans = INFS;

    for (int i = 0; i < n; i++)

        ans = min(ans, dp[i][ENDS]);

    return ans;

}



int main() {

    int cases;

    scanf("%d", &cases);

    while (cases--) {

        int n;

        scanf("%d", &n);

        for (int i = 0; i < n; i++)

            scanf("%d%d%d%d%d", &rect[i].x1, &rect[i].y1, &rect[i].x2, &rect[i].y2, &rect[i].color);

        printf("%d
", workout(n));

    }

    return 0;

}