POJ 2836 Rectangular Covering 题解 《挑战程序设计竞赛》

POJ 2836 Rectangular Covering

铺地板：坐标平面上有n各点，用任意大小（非零）的地板砖覆盖它们，求最省的地板砖总面积。

3.4熟练掌握动态规划

状态压缩DP

先预处理数据，将n个点两两组合形成n * (n-1) / 2个矩形，计算每个矩形的面积和内部点个数。

接着利用预处理数据来枚举，定义

dp[S] := 矩形集为S时的最省面积

先假设平面上没有矩形，那么dp[0]=0，接着一个一个地往平面上加矩形，递推关系是：

dp[新矩形集合] = min(dp[新矩形集合], dp[旧矩形集合] + 新矩形的面积);

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string.h>

#define MAX_N 16
int x[MAX_N], y[MAX_N], dp[1 << MAX_N]; // dp[S] := 点集为S时的最省面积
using namespace std;

struct Rect
{
    int coverd; // 内含点集
    int area;   // 面积

    Rect(const int& coverd, const int& area) : coverd(coverd), area(area)
    {}

    void add(int i)
    {
        coverd |= 1 << i;
    }
};

/**
* 点k是否在点i和点j围成的矩形中
*/
bool is_in(int i, int j, int k)
{
    return ((x[i] - x[k]) * (x[j] - x[k]) <= 0) && ((y[i] - y[k]) * (y[j] - y[k]) <= 0);
}


int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int n;
    while(cin >> n && n)
    {
        for (int i = 0; i < n; ++i)
        {
            cin >> x[i] >> y[i];
        }
        vector<Rect> rarray;
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                Rect r((1 << i) | (1 << j), max(1, (int const &) abs(x[i] - x[j])) * max(1, (int const &) abs(y[i] - y[j])));
                for (int k = 0; k < n; ++k)
                {
                    if(is_in(i, j, k))
                    {
                        r.add(k);
                    }
                }
                rarray.push_back(r);
            }
        }
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;  // 包含0个点的矩形的面积是0
        for (vector<Rect>::iterator it = rarray.begin(); it != rarray.end(); ++it)
        {
            for (int s = 0; s < 1 << n; ++s)
            {
                int ns = s | it->coverd;
                if (dp[s] != 0x3f3f3f3f && ns != s)
                {
                    dp[ns] = min(dp[ns], dp[s] + it->area);
                }
            }
        }
        cout << dp[(1 << n) - 1] << endl;
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2836 Rectangular Covering 题解 《挑战程序设计竞赛》