• POJ 2836 Rectangular Covering 状态压缩DP(铺砖问题)


    一、题目大意

    坐标系中有n个点,它们满足 -1000<=x<=1000,-1000<=y<=1000。

    现在要在坐标系中放一些矩形,要使得每个点都被矩形覆盖(被矩形的边或者顶点覆盖也可以),每个矩形都必须满足面积大于0,且每个矩形最少要覆盖两个点。

    请你输出覆盖所有点时,如何使所有矩形的面积和最小,输出这个面积和。

    二、解题思路

    我们可以从左上角的点开始,一点点的覆盖到右下角的点。

    那么对于第 i 个点,我们可以认为

    1、i 以前的点都被覆盖;

    2、如果 i 还未被覆盖,则它必须被覆盖。

    同时思考下,当铺设到第 i 个点时,对于覆盖情况固定时,铺完剩下的点需要的最小矩形面积是固定的。

    则可以定义DP数组,DP[S][i]代表已经铺设的点的集合为S时,铺设好第 i 个点到最后一个点所需要的最小的矩形面积。

    对于最后一个点n-1,如果S包含n-1,则DP[S][n-1]=0,如果不包含,那么DP[S][n-1]=点n-1到其余点的矩形的面积的最小值

    那么借助这个思路,我们就可以展开循环,外层放 i ,从 n - 1 到 0循环,内层放 S,从 1 到 (1<

    如果S不包含 i ,就循环其他所有点 j (i != j),

    DP[S][i]=min(DP[S][i],DP[S 添加 i 添加 j][i+1]+i和j组成的矩形面积)

    思路可以了,但欠缺一点,有时候一个矩形会覆盖两个点。

    这种情况仅在两个点同行或同列的情况出现,否则是下图

    那么加个判断,如果两个点是同一条直线,它们之间的矩形为零的那条边设置长度为1。同时连一条边的时候,判断是否有其他点是否也在矩形内的,记录它们到集合child里,更改递推式为

    DP[S][i]=min(DP[S][i],DP[S 添加 i 添加 j 添加child内所有的元素][i+1]+i和j组成的矩形面积)

    (这里只判断 i 之后的点是否在范围内即可,因为之前的不会影响到DP[XXX][i+1]之后的值)

    循环集合时,要跳过确定已经连了的部分来提速。

    三、代码

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. struct P
    6. {
    7. int x, y;
    8. P(int x = 0, int y = 0) : x(x), y(y) {}
    9. };
    10. bool compare(P &a, P &b)
    11. {
    12. return a.y != b.y ? a.y > b.y : a.x < b.x;
    13. }
    14. const int MAX_N = 15;
    15. const int INF = 0x3f3f3f3f;
    16. int dp[2][1 << MAX_N];
    17. P dat[15];
    18. int n;
    19. int *crt = dp[0], *nxt = dp[1];
    20. void solveItem(int i, int used)
    21. {
    22. if (used >> i & 1)
    23. {
    24. nxt[used] = crt[used];
    25. return;
    26. }
    27. nxt[used] = INF;
    28. for (int j = 0; j < n; j++)
    29. {
    30. if (i == j)
    31. {
    32. continue;
    33. }
    34. int w = abs(dat[i].x - dat[j].x);
    35. int h = abs(dat[i].y - dat[j].y);
    36. int x1 = min(dat[i].x, dat[j].x);
    37. int y1 = min(dat[i].y, dat[j].y);
    38. int area = (w > 0 ? w : 1) * (h > 0 ? h : 1);
    39. int child = 0;
    40. for (int k = i + 1; k < n; k++)
    41. {
    42. if ((dat[k].x >= x1 && dat[k].x <= (x1 + w) && dat[k].y >= y1 && dat[k].y <= (y1 + h)) ||
    43. (w == 0 && dat[k].x >= (x1 - 1) && dat[k].x <= x1 && dat[k].y >= y1 && dat[k].y <= (y1 + h)) ||
    44. (h == 0 && dat[k].y >= (y1 - 1) && dat[k].y <= y1 && dat[k].x >= x1 && dat[k].x <= (x1 + w)))
    45. {
    46. child = child | (1 << k);
    47. }
    48. }
    49. nxt[used] = min(nxt[used], crt[used | (1 << i) | (1 << j) | child] + area);
    50. }
    51. }
    52. void solve()
    53. {
    54. memset(dp, 0, sizeof(dp));
    55. int all = (1 << n) - 1;
    56. for (int i = n - 1; i >= 0; i--)
    57. {
    58. all = all & ~(1 << i);
    59. for (int S = 0; S < (1 << (n - i)); S++)
    60. {
    61. int used = all | (S << i);
    62. solveItem(i, used);
    63. }
    64. swap(crt, nxt);
    65. }
    66. printf("%d\n", crt[0]);
    67. }
    68. int main()
    69. {
    70. while (true)
    71. {
    72. scanf("%d", &n);
    73. if (n == 0)
    74. {
    75. break;
    76. }
    77. for (int i = 0; i < n; i++)
    78. {
    79. scanf("%d%d", &dat[i].x, &dat[i].y);
    80. }
    81. sort(dat, dat + n, compare);
    82. solve();
    83. }
    84. return 0;
    85. }

  • 相关阅读:
    【行为型模式】模板方法模式
    Silk.Net Opengl 创建基于WPF或者Winform 的显示控件
    面向对象思想
    一次 Jedis 参数异常引发服务雪崩
    Games 103 作业二
    相机HAL
    OA项目之我的审批(查询&会议签字)
    结合paper 详细解读yolact源码
    带你玩转CompletableFuture异步编程
    JVM学习(三)--生产环境的线程问题诊断
  • 原文地址:https://blog.csdn.net/qq_53038151/article/details/134418457