首页 > 代码库 > poj - 2836 - Rectangular Covering(状态压缩dp)
poj - 2836 - Rectangular Covering(状态压缩dp)
题意:平面上有 n (2 ≤ n ≤ 15) 个点,现用平行于坐标轴的矩形去覆盖所有点,每个矩形至少盖两个点,矩形面积不可为0,求这些矩形的最小面积。
题目链接:http://poj.org/problem?id=2836
——>>因为每个矩形至少要盖两个点,所以,枚举所有的两点组合。。
状态:dp[S] 表示将集合 S 中的所有点覆盖的最小矩形面积
状态转移方程:dp[news] = min(dp[news], dp[S] + r[i].area);
此题为重复覆盖,非精确覆盖,转移时用S ^ r[i].cover是不正确的。。
#include <cstdio> #include <algorithm> #include <cstring> #include <vector> using std::vector; using std::min; using std::max; const int MAXN = 15; const int INF = 0x3f3f3f3f; struct POINT { int x; int y; } p[MAXN + 1]; struct RECTANGLE { int area; int cover; } r[MAXN * MAXN]; int n; int dp[1 << MAXN]; int area[MAXN + 1][MAXN + 1]; int cnt; int abs(int x) { return x > 0 ? x : -x; } void Read() { for (int i = 0; i < n; ++i) { scanf("%d%d", &p[i].x, &p[i].y); } } void Init() { cnt = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if (j != i) { int width = abs(p[i].x - p[j].x) == 0 ? 1 : abs(p[i].x - p[j].x); int height = abs(p[i].y - p[j].y) == 0 ? 1 : abs(p[i].y - p[j].y); r[cnt].area = width * height; r[cnt].cover = 0; for (int k = 0; k < n; ++k) { if (p[k].x >= min(p[i].x, p[j].x) && p[k].x <= max(p[i].x, p[j].x) && p[k].y >= min(p[i].y, p[j].y) && p[k].y <= max(p[i].y, p[j].y)) { r[cnt].cover |= (1 << k); } } ++cnt; } } } } void Dp() { memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; for (int S = 0; S < (1 << n); ++S) { if (dp[S] != INF) { for (int i = 0; i < cnt; ++i) { int news = S | r[i].cover; if (news != S) { dp[news] = min(dp[news], dp[S] + r[i].area); } } } } printf("%d\n", dp[(1 << n) - 1]); } int main() { while (scanf("%d", &n) == 1 && n) { Read(); Init(); Dp(); } return 0; }
poj - 2836 - Rectangular Covering(状态压缩dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。